Longest increasing subsequence
MediumStuck?
Show a hintHide the hint
Keep the smallest value that can end an increasing run of each length. That list stays sorted, so each new value can be placed by binary search.
The idea behind this problem
Last problem in this lesson
Go to the next lessonGiven an array of integers, return the length of the longest strictly increasing subsequence.
A subsequence keeps the original order but may skip elements. The quadratic solution is the obvious one; the intended solution runs in O(n log n).
Constraints#
1 <= n <= 200000-10^9 <= nums[i] <= 10^9
Input
nums is a count then that many integers.
Output
A single integer, the length of the longest increasing subsequence.
Examples
Input
8 10 9 2 5 3 7 101 18
Output
4
`2 3 7 101` is one of the longest increasing subsequences.
Input
6 7 7 7 7 7 7
Output
1
Strictly increasing, so equal values cannot extend a subsequence.
Something wrong with this problem? Report an issue
Ready to try it
Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.
Free, and it stays free. No card.