Вызов 100 литкодов: №5

#300 Самая длинная возрастающая подпоследовательность

Проблема

Учитывая целочисленный массив nums, вернуть длину самой длинной строго возрастающей подпоследовательности.

Подпоследовательность – это последовательность, которая может быть получена из массива путем удаления некоторых элементов или их отсутствия без изменения порядка оставшихся элементов. Например, [3,6,2,7] является подпоследовательностью массива [0,3,1,6,2,2,7].

Пример 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Пример 2:

Input: nums = [0,1,0,3,2,3]
Output: 4

Псевдокод

Мы используем восходящие алгоритмы для построения массива самого длинного растущего подмассива:

1. Цикл по массиву nums с двумя указателями i и j
2. Указатель j указывает число, которое мы используем для сравнения с номером указателя i.
3. Если nums[j] ‹ nums[i] означает, что мы можем выбрать номер указателя j
4. Если мы выберем nums[j], самая длинная возрастающая длина подмассива, которую мы можем получить, будет наибольшей увеличивающейся длиной подмассива при выборе nums[j] + nums[i]
5. Если мы не выбираем nums[j], самая длинная увеличивающаяся длина подмассива, которую мы можем получить, будет самой длинной возрастающей длиной подмассива i

Код