Harddynamic programmingbinary search
Longest Increasing Subsequence
Find the longest strictly increasing subsequence, which need not be contiguous.
Return the length of the longest strictly increasing subsequence of nums.
A subsequence keeps the original order but may skip any number of elements — it does not have to be contiguous.
Constraints
- 1 ≤ nums.length ≤ 100,000
- -10⁹ ≤ nums[i] ≤ 10⁹
O(n²) will time out!
Examples
- Input
- nums = [10,9,2,5,3,7,101,18]
- Output
- 4
- Why
- [2, 3, 7, 18].
- Input
- nums = [0,1,0,3,2,3]
- Output
- 4
- Why
- [0, 1, 2, 3].
- Input
- nums = [7,7,7,7]
- Output
- 1
- Why
- Strictly increasing, so equal values cannot extend a run.
Submitting also runs 7 hidden tests.
Limits
2000 ms and 256 MB per test case.