Longest Increasing Subsequence
Longest Increasing Subsequence is a medium 1-D Dynamic Programming problem from the Blind 75. The key pattern is patience sorting, and a good solution runs in O(n log n) time.
Problem
Return the maximum length of a strictly increasing subsequence.
Examples
Example 1
Input
[5,1,6,2,3,4]Output
4Example 2
Input
[9,1,8,2,7,3]Output
3Example 3
Input
[2,5,1,6,3,7]Output
4Approach
Keep the smallest possible tail for every subsequence length and place each value with a binary search. The number of tails is the answer.
| Pattern | Patience sorting |
|---|---|
| Time | O(n log n) |
| Space | O(n) |
Watch out for
Strictly increasing means equal values replace a tail instead of extending.