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
[50, 3, 10, 7, 40, 80] is
[3, 7, 40, 80].
- 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?