Codeforces 1741E Sending a Sequence - Transition Case 1

The transition: Compute dp[i] from earlier values.

Case 1: Length on the left When you're at position i, maybe the last block ends here, and it has the length on the left side. That means the block looks like: $[L, x_1, x_2, \dots, x_L]$

So if b[j] = L and j + L = i, then we can form a block from position j to i. Here's how you check: if b[j] = i - j for some j < i, and dp[j-1] = true , then dp[i] = true.

look back from position i. Each position j where b[j] = i - j, check if dp[j-1] is true. If yes, you found a valid block ending at i. But checking every j takes $O(n)$ per position. That's $O(n^2)$ total. Can you do better?