Codeforces 977F Consecutive Subsequence - Transition

2. Transition

For each element a[i] = x:

$\Rightarrow$ Compute the best subsequence that can end at x

• $len_i = dp[x-1] + 1$

$\Rightarrow$ 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

$\Rightarrow$ Update dp[$x$] if you improved it

If this new subsequence is better:

• dp[x] = len_i
• last_pos[x] = i

$\Rightarrow$ Update global best

If dp[x] is the largest seen:

• best_len = dp[x]
• best_end = i