Increasing Subsequences and Cuts

Shape A: the choice depends on your last pick

Longest increasing subsequence: pick numbers in order, each bigger than the last one you picked.

It’s take or skip, but you may take a[i] only if it is bigger than your last pick. So the call must remember that last pick.

• Promise: f(i, prev) = longest increasing subsequence from a[i..], when the last pick is a[prev] (prev = −1 means none yet).
• Base case: i == n → 0.
• Choices: skip → f(i + 1, prev). Take (if prev == -1 || a[i] > a[prev]) → 1 + f(i + 1, i).
• Memo: int[n][n + 1], used as memo[i][prev + 1] (shift by one, because −1 can’t be an index). Time O(n²).