Longest Increasing Subsequence
MediumDynamic Programming
You are given an integer array nums. Return the length of the longest strictly increasing subsequence.
A subsequence keeps the original order of the elements it uses but may skip any elements in between (it does not have to be contiguous). Strictly increasing means each chosen element is greater than the one before it, so equal values cannot both be used.
Example 1
- Input:
- nums = [-1, 3, 4, -2, 0, 6, 2, 3]
- Output:
- 4
- Explanation
-1, 3, 4, 6and-2, 0, 2, 3are both increasing subsequences of length 4, and no length-5 one exists.
Example 2
- Input:
- nums = [4, 10, 4, 3, 8, 9]
- Output:
- 3
- Explanation
4, 8, 9works.4, 10cannot be extended because everything after10is smaller.
Example 3
- Input:
- nums = [5, 5, 5, 5]
- Output:
- 1
- Explanation
- Equal values do not count as increasing, so the best is any single element.
Constraints
- 1 ≤
nums.length≤ 2500 - -104 ≤
nums[i]≤ 104