Longest Increasing Subsequence
Problem statement
Given an array of $n$ integers, find the length of the longest strictly increasing subsequence. A subsequence is derived from the array by deleting some (or no) elements without changing the order of the remaining elements.
Design an $O(n \log n)$-time algorithm. Specifically:
- Describe the algorithm and explain the invariant maintained by the auxiliary "tails" array.
- Show how to reconstruct one actual longest increasing subsequence (not just its length) while keeping time $O(n \log n)$ and extra space $O(n)$.
Constraints:
- $1 \leq n \leq 10^5$
- $-10^4 \leq \text{nums}[i] \leq 10^4$
- Subsequence must be strictly increasing
Example 1:
- Input:
nums = [3, 1, 4, 1, 5, 9, 2, 6] - Output:
4 - Explanation: One longest increasing subsequence is $[1, 4, 5, 9]$. Others of length 4 exist, e.g., $[1, 4, 5, 6]$.
Example 2:
- Input:
nums = [10, 9, 2, 5, 3, 7, 101, 18] - Output:
4 - Explanation: One LIS is $[2, 3, 7, 101]$. Another is $[2, 5, 7, 18]$.
Example 3:
- Input:
nums = [7, 7, 7, 7] - Output:
1 - Explanation: All elements are equal, so the longest strictly increasing subsequence has length 1.
Show hint
For each possible subsequence length, which single number summarizes everything you need to know to extend it later?
Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.