Longest Increasing Subsequence
Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.
For example, the length of LIS
for [50, 3, 10, 7, 40, 80]
is 4
and LIS
is [3, 7, 40, 80]
.
Example 1:
Input | 10 | 9 | 2 | 5 | 3 | 7 | 101 | 18 |
---|---|---|---|---|---|---|---|---|
LIS | 1 | 2 | 3 | 4 | ||||
Output | 4 |
Example 2:
Input | 10 | 22 | 9 | 33 | 21 | 50 | 41 | 60 | 80 |
---|---|---|---|---|---|---|---|---|---|
LIS | 1 | 2 | 3 | 4 | 5 | 6 | |||
Output | 6 |
Note:
- There may be more than one LIS combination, it is only necessary for you to return the length.
- Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?
Try it yourself
Loading full content...