longest_increasing_subsequence

README

< Previous 　　　　　　　　　　　　　　　　 Next >

300. Longest Increasing Subsequence (Medium)

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. 

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(n²) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Related Topics

[Binary Search] [Dynamic Programming]

Similar Questions

1. Increasing Triplet Subsequence (Medium)
2. Russian Doll Envelopes (Hard)
3. Maximum Length of Pair Chain (Medium)
4. Number of Longest Increasing Subsequence (Medium)
5. Minimum ASCII Delete Sum for Two Strings (Medium)