Longest Strictly Increasing Subsequence
You get an integer array nums.
A subsequence is what is left after you delete zero or more elements. The elements that stay keep their original order. They do not need to be next to each other.
A subsequence is strictly increasing when every element is greater than the one before it. Two equal values next to each other are not allowed.
Return the length of the longest strictly increasing subsequence of nums. If nums is empty, return 0.
Hint
For each index i, find the longest increasing subsequence that ends at i. It is one more than the best answer among earlier indices with a smaller value. That gives O(n²). A faster O(n log n) method keeps, for each length, the smallest possible last value, and uses binary search to update it.
Examples
Example 1
- Input:
- [7,2,9,3,4,1,8]
- Output:
- 4
One longest choice is 2, 3, 4, 8. No strictly increasing subsequence of length 5 exists.
Example 2
- Input:
- [5,5,5,6]
- Output:
- 2
Equal values cannot follow each other, so the best is one 5 and then 6.
Example 3
- Input:
- [12,9,4,-3]
- Output:
- 1
The values only go down, so any single element is the longest choice.
Constraints
0 <= nums.length <= 40-100 <= nums[i] <= 100
Run checks your code against the 3 examples. Submit checks it against all 263 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.