The idea
Sometimes the effect of taking an item depends on something besides the position: whether the number of items taken so far is even or odd, how many of a limited resource were used, which mode you are in.
Make that extra fact part of the state. f[i][s] is then the best result over the first i items while being in situation s, and each transition says how s changes.
The price is a table multiplied by the number of situations, so keep that number small.
Sample problem
1911. Maximum Alternating Subsequence Sum ↗ Medium
Choose a subsequence. Its alternating sum adds the 1st, 3rd, 5th… chosen numbers and subtracts the 2nd, 4th…. Return the largest alternating sum.
nums = [6,2,1,2,4,5] output = 10 (6 − 1 + 5)
Why the solution works
Whether a number is added or subtracted depends on how many numbers were chosen before it. A state that only says “how far along the array” forgets that, so it cannot decide the sign.
Add what is missing as a second dimension: the parity of the count chosen so far. even is the best sum with an even count, odd with an odd count.
Each number x has three options: skip it; become the next odd pick (even + x); become the next even pick (odd − x). Both new values are computed from the old ones before either is overwritten.
Complexity: O(n) time, O(1) memory.
Watch out
- Unreachable states must start at −INF (or +INF), not 0, or they leak into the answer.
- Each extra dimension multiplies time and memory; check the total before coding.
- When row i only reads row i−1, two rows are enough.