Longest Increasing Subsequence — Step-by-Step Visualization

Algorithm Pattern

Dynamic Programming

Key Idea

We can define `dp[i]` as the length of the longest increasing subsequence that ends with the element at index `i`. To calculate `dp[i]`, we look at all previous indices $j < i$ where $nums[j] < nums[i]$ and take the maximum `dp[j] + 1`.

Step-by-Step Approach

1. Initialize an array `dp` of the same length as `nums` with all 1s.
2. Iterate through the array with index `i` from 1 to $n-1$.
3. For each `i`, iterate through all $j < i$.
4. If $nums[j] < nums[i]$, update `dp[i] = max(dp[i], dp[j] + 1)`.
5. The final answer is the maximum value in the `dp` array.

Common Gotchas

• The subsequence doesn't have to be contiguous.
• Strictly increasing means $nums[j] < nums[i]$, not $nums[j] le nums[i]$.