Longest increasing subsequence
Why it exists
Problem: Finding the longest increasing subsequence by generating all 2^n possible subsequences and validating them takes exponential time.
Better idea: At each element, look back at all previous elements. If a previous element is strictly smaller, you can attach the current element to its longest subsequence. This reduces the problem to an O(n^2) search over previous states.
Mental model
Build chains. At each new number, scan backwards: 'who is smaller than me?' Pick the smaller number that already has the longest chain, and add yourself to it.
Maintain an array where each cell tracks the longest increasing subsequence that strictly ends at that index. To fill a cell, iterate through all preceding indices. If the preceding value is smaller than the current value, it's a valid chain to extend. Take the maximum of all valid extensions.
Repeated decision: for this element, which earlier element (with a smaller value) gives the longest chain I can extend, or do I start fresh here?
Explanation
To solve Longest Increasing Subsequence (LIS), we must define our state precisely: `dp[i]` is the length of the longest strictly increasing subsequence ENDING AT index `i`.
Note the emphasis: it does not mean 'the longest in the first `i` elements'. It must include `nums[i]` as its final element. This forces the sequence to anchor, allowing future elements to correctly check if they can append to it.
The recurrence relation requires a search over all previous states:
`dp[i] = 1 + max(dp[j])` for all `j < i` where `nums[j] < nums[i]`.
If no such `j` exists, `dp[i] = 1` (the element forms a sequence of length 1 by itself).
The base case is simple: initialize the entire `dp` array to 1, since every element is a valid increasing subsequence of length 1 on its own.
Because computing `dp[i]` requires scanning `i` previous elements, computing the whole array takes `O(n^2)` time. The space complexity is `O(n)` to store the array.
Importantly, the final answer is NOT `dp[n-1]`. Because the longest sequence could end anywhere in the array, the answer is `max(dp)` over the entire array.
It is possible to solve LIS in `O(n log n)` time using a patience-sorting technique that maintains a 'tails' array and uses binary search. That is a fundamentally different approach utilizing binary search, while the `O(n^2)` DP approach explicitly demonstrates how recurrences can require dynamic-width lookbacks.
Let's trace `nums = [3, 4, -1, 5, 8, 2]`. We initialize `dp = [1, 1, 1, 1, 1, 1]`.
- **i=0 (3):** No prior elements. `dp[0] = 1`.
- **i=1 (4):** Checks prior element 3. `3 < 4`, so `dp[1] = max(1, dp[0] + 1) = 2`.
- **i=2 (-1):** Checks 3 and 4. Neither is smaller than -1. `dp[2] = 1`.
- **i=3 (5):** Checks 3 (`dp[0]=1`), 4 (`dp[1]=2`), and -1 (`dp[2]=1`). All are smaller. Extending from 4 gives the longest chain: `dp[1] + 1 = 3`. `dp[3] = 3`.
- **i=4 (8):** Checks 3, 4, -1, and 5. All are smaller. Extending from 5 gives the longest chain: `dp[3] + 1 = 4`. `dp[4] = 4`.
- **i=5 (2):** Checks prior elements. Only -1 is smaller. Extending from -1 gives `dp[2] + 1 = 2`. `dp[5] = 2`.
Our final array is `[1, 2, 1, 3, 4, 2]`. The final answer is the maximum value in the entire array, which is `4` (the sequence 3, 4, 5, 8). It is explicitly NOT `dp[5] = 2`, because the longest sequence does not have to end at the last index.
Key points
- State Definition: `dp[i]` is the length of the LIS ending precisely at index `i`.
- Final Answer Extraction: Since the sequence can end at any index, you must iterate over the completed `dp` array and find the maximum value, rather than just returning the last element.
- O(n^2) Complexity: Unlike 1D DP problems that only look back 1 or 2 steps, LIS requires scanning all `j < i` for every element, resulting in quadratic time.
Common mistakes
- Misinterpreting the state: Assuming `dp[i]` means 'longest sequence using the first `i` elements' rather than 'ending at index `i`'. If it didn't end at `i`, you wouldn't know which value to compare the next element against.
- Confusing subsequence with subarray: A subarray must be contiguous (e.g., longest increasing run). A subsequence can skip elements. LIS handles skipped elements by scanning all previous indices.
Recall questions
- What is the exact definition of the state `dp[i]` in the LIS DP approach?
- How do you find the final answer after filling the LIS `dp` array?
- What is the time complexity of the standard DP approach to LIS?
Questions & answers
Find the maximum sum of an increasing subsequence.
Change the state to store the maximum sum ending at index `i` instead of the length. `dp[i] = nums[i] + max(dp[j])` where `nums[j] < nums[i]`.
Approach: The identical O(n^2) scanning structure works, just accumulating sums rather than lengths.
Given a sequence of Russian Doll envelopes, find the maximum number of envelopes you can nest inside each other.
Sort the envelopes by width ascending, and height descending for ties, then find the LIS on the heights.
Approach: Sorting reduces a 2D nesting problem to a standard 1D LIS problem.
Continue learning
Previous: 0/1 Knapsack