PythonHardDynamic Programming35 min
Find the longest strictly increasing subsequence length
Subsequence elements retain original order but need not be contiguous. Equal values cannot extend a strictly increasing subsequence; empty input returns zero. Interviewers use this problem to assess binary-search the smallest tail that is at least the new value.
Input
First line: n. Second line: n space-separated integers (empty when n = 0).
Output
Print the result on one line; print an empty line for an empty string.
Constraints
0 <= n <= 100000; -10^9 <= each value <= 10^9.
Example
Input
8 10 9 2 5 3 7 101 18
Output
4
Example 2 input
5 5 4 3 2 1
Output
1
A descending array has no increasing pair.
Public test cases (2)
Input
8 10 9 2 5 3 7 101 18
Expected output
4
Input
6 0 1 0 3 2 3
Expected output
4
Hints (2)
- Identify the state needed to avoid repeated work.
- Binary-search the smallest tail that is at least the new value.
Target complexity: time O(n log n) · space O(n)