Longest Increasing Subsequence
medium1-D Dynamic ProgrammingO(n^2) DP (or patience sorting + binary search)B75Solve on LeetCode#300
Given an integer array nums, return the length of its longest strictly increasing subsequence. A subsequence keeps the original order but may skip elements — [2, 5, 7] is a subsequence of [2, 9, 5, 1, 7]. "Strictly increasing" means each element must be larger than the one before it, so equal values cannot both be used.
Constraints: 1 <= nums.length <= 2500, -10^4 <= nums[i] <= 10^4.
Examples
- Input:
- nums = [10, 9, 2, 5, 3, 7, 101, 18]
- Output:
- 4
One longest increasing subsequence is [2, 3, 7, 101]; [2, 5, 7, 18] also works.
- Input:
- nums = [0, 1, 0, 3, 2, 3]
- Output:
- 4
[0, 1, 2, 3].
- Input:
- nums = [7, 7, 7, 7]
- Output:
- 1
Strictly increasing forbids equal neighbors, so no chain is longer than a single 7.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.