mediumDynamic programming, 1D target 25 min
Longest increasing subsequence
You get a list of integers nums. A subsequence keeps some of the items in their original order and drops the rest; the kept items do not have to be neighbors.
Return the length of the longest subsequence that is strictly increasing: every item is bigger than the one before it. Equal items do not count as increasing.
Example 1
Input
nums = [5, 2, 8, 6, 3, 6, 9, 7]Output4One longest is 2, 3, 6, 9, from positions 1, 4, 5 and 6. Another is 2, 3, 6, 7. None has 5 items.
Example 2
Input
nums = [4, 4, 4]Output1Equal items are not increasing, so the best is a single item.
Example 3
Input
nums = [1, 5, 2, 3]Output31, 2, 3 skips the 5. The longest rising stretch of neighbors, [1, 5] or [2, 3], has only 2 items.
Constraints
1 ≤ len(nums) ≤ 2,500
-104 ≤ nums[i] ≤ 104
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.
Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.