2. Transition
For each element a[i] = x:
Compute the best subsequence that can end at x
Set the predecessor
- If a subsequence ended at
x-1,prev[i] = last_pos[x - 1] - Otherwise, this starts a new subsequence:
prev[i] = -1
Update dp[] if you improved it
If this new subsequence is better:
dp[x] = len_ilast_pos[x] = i
Update global best
If dp[x] is the largest seen:
best_len = dp[x]best_end = i