Учитывая целочисленный массив 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
Пример 3:
Input: nums = [7,7,7,7,7,7,7] Output: 1
Как всегда, следите за комментариями к каждой строке.
В этом решении временная сложность равна O(n²), так как мы используем вложенный цикл. А пространственная сложность — O(n), размер массива count равен входным числам.
Судя по моим комментариям к коду, если у вас есть какие-либо вопросы или комментарии, не стесняйтесь обращаться к нам.