Given an integer array nums, return the length of its longest strictly increasing subsequence.
A subsequence keeps the original order but may skip elements: [3, 6, 2, 7] is a subsequence of [0, 3, 1, 6, 2, 2, 7].
Examples
Example 1
- Input
- nums = [10, 9, 2, 5, 3, 7, 101, 18]
- Output
- 4
- Why
- One longest increasing subsequence is [2, 3, 7, 101].
Example 2
- Input
- nums = [0, 1, 0, 3, 2, 3]
- Output
- 4
Example 3
- Input
- nums = [7, 7, 7, 7, 7, 7, 7]
- Output
- 1
Constraints
1 <= nums.length <= 2500-10^4 <= nums[i] <= 10^4