133. Longest Increasing Subsequence
Choose positions in their original order so the selected values increase strictly from one selection to the next. You may skip positions and want the greatest number of selected values.
A subsequence need not be contiguous. Equal selected values cannot extend a strictly increasing sequence.
Example 1
Input
nums=[10,9,2,5,3,7,101,18]
Output
4
Explanation: One witness is [2,3,7,18]. The answer does not require returning a witness.
Example 2
Input
nums=[2,2,2]
Output
1
Explanation: Equal values replace the same endpoint rather than extending a strict sequence.
Example 3
Input
nums=[3,5,6,2,4]
Output
3
Explanation: The final minimum tails are [2,4,6], but those values do not occur in that order. [3,5,6] is a valid length-three witness.
Example 4
Input
nums=[]
Output
0
Explanation: There is no selected value.
Constraints
0 <= nums.length <= 105-231 <= nums[i] <= 231 - 1
Hints
Hint 1
For two subsequences of equal length, which endpoint is easier for future values to extend?
Hint 2
Store the minimum endpoint for every attainable length and examine whether these endpoints are sorted.
Hint 3
Replace the first tail ≥x; append only when x is larger than all active tails.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Minimum tails need not coexist as a witness
[3,5,6,2,4]
3