LeetCode 300 Longest Increasing Subsequence - Transition

To compute $dp[i]$, look at all indices $j < i$. If $arr[j] < arr[i]$, you can extend the subsequence ending at $j$ by adding $arr[i]$. The formula (how dp[i] depends on earlier dp values): $dp[i] = \max(dp[j] + 1)$ for all $j < i$ where $arr[j] < arr[i]$ If no such $j$ exists, $dp[i]$ stays at 1.

The final answer is $\max(dp[i])$ for all $i$, not just $dp[n-1]$. The longest subsequence might end anywhere. This formula captures how dp[i] builds on dp[j] for earlier indices.