Longest Increasing Subsequence
Medium · Dynamic Programming · Array · Dynamic Programming · Binary Search
Problem
Return the length of the longest strictly increasing subsequence of nums. A subsequence keeps the original order but need not be contiguous.
Examples
Input: nums = [10,9,2,5,3,7,101,18] Output: 4
2, 3, 7, 101.
Input: nums = [7,7,7,7] Output: 1
Strictly increasing, so repeats do not extend anything.
Constraints
- 1 <= len(nums) <= 2500
- -10^4 <= nums[i] <= 10^4
Approaches
- Quadratic dynamic programming — time O(n²), space O(n)
Follow-up
Can you bring the running time down to O(n log n)?
Related problems
Start free on Cariara · Coding problems · System design studio
