Longest Increasing Subsequence in O(n log n)
Problem statement
Given an array of integers $a_1, a_2, \ldots, a_n$, find the length of the longest strictly increasing subsequence (LIS).
A subsequence is strictly increasing if each element is greater than the one before it -- elements need not be contiguous.
Requirements:
- Implement the patience-sorting approach: maintain a list of "pile tops" and use binary search to place each new element. Return the number of piles at the end.
- Explicitly handle duplicate values in the input (remember: the subsequence must be strictly increasing, so duplicates cannot both appear).
- Argue why this algorithm is correct -- why does the number of piles equal the LIS length?
Constraints:
- $1 \leq n \leq 10^5$
- $-10^4 \leq a_i \leq 10^4$
- Target: $O(n \log n)$ time, $O(n)$ space
Examples:
- Input:
[10, 9, 2, 5, 3, 7, 101, 18]-- Output:4(the LIS is[2, 3, 7, 101]or[2, 5, 7, 101]) - Input:
[0, 1, 0, 3, 2, 3]-- Output:4(the LIS is[0, 1, 2, 3]) - Input:
[7, 7, 7, 7, 7]-- Output:1(all duplicates, no two can both appear in a strictly increasing subsequence)
Show hint
For each possible subsequence length, what is the most useful single number to remember about all runs of that length?
Relevant roles: ML Engineer, AI Engineer, Forward Deployed Engineer and LLM Engineer.