##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
The recurrence
To compute , look at all indices . If , you can extend the subsequence ending at by adding . The formula (how dp[i] depends on earlier dp values): for all where If no such exists, stays at 1.
The final answer is for all , not just . The longest subsequence might end anywhere. This formula captures how dp[i] builds on dp[j] for earlier indices.
