A subsequence keeps some of the items of a list, in their original order, and drops the rest:
[3, 7] is a subsequence of [3, 1, 7], but [7, 3] is not.
Given a list of integers nums, return the length of its longest subsequence whose values
strictly increase from left to right.
Example 1
- Input
- nums = [4, 10, 4, 3, 8, 9]
- Output
- 3
[4, 8, 9] is one; [3, 8, 9] is another.Example 2
- Input
- nums = [0, 8, 4, 12, 2, 10, 6, 14]
- Output
- 4
[0, 4, 10, 14] is one of several of length 4.Example 3
- Input
- nums = [5, 5, 5]
- Output
- 1
Constraints
numsholds 1 to 2500 numbers.- −10⁴ ≤
nums[i]≤ 10⁴
Show the pattern
Dynamic programming (1D), Binary search
The longest increasing run that ends at a position extends the best run ending at some earlier, smaller value: one answer per position, each built from the answers before it.
See dynamic programming (1d) in a visualiserShow the approach
The direct table: let ends[i] be the length of the longest increasing subsequence that ends at
position i. It extends the best one ending at an earlier, smaller value, so
ends[i] = 1 + max(ends[j]) over j < i with nums[j] < nums[i] (or 1 if there is none). The
answer is the largest entry. That is O(n²), fast enough here.
The O(n log n) version keeps tails, where tails[k] is the smallest value that ends an
increasing subsequence of length k + 1 seen so far. A smaller ending is always at least as good,
because more values can follow it. tails stays sorted, so for each value x, binary search for
the first tail that is at least x: replace it with x, or append x when every tail is
smaller (the longest subsequence just grew by one). The answer is the length of tails.
Time: O(n log n) · Space: O(n)