State Machine DP

At a glance

The instinct

Some sequence problems are not about which items you pick but about what mode you are in when you meet each item. In the stock problems you are either holding a share or not, maybe cooling down, maybe on your second transaction. The legal moves depend only on the current mode, not on the full history. So draw the modes as circles, the moves as arrows, and keep best[mode] for "best result so far if I am in this mode right now". Walking the array is just firing every arrow once per element.

Recognise it

Not this pattern if...

• The choice at step i depends on an arbitrary earlier index, not just the current mode (that is LIS / 2D DP).
• There is only one mode - plain Kadane or a running min is enough (Best Time to Buy and Sell Stock, one transaction).
• Items can be taken in any order (that smells like knapsack or bitmask DP).

Memory hack

Analogy: a traffic light. It can only go green → yellow → red → green; you never jump from yellow to green. A cooldown is just a mandatory yellow light between "sold" and "can buy again".

DP framing:

• State - best[mode] after processing the first i elements.
• Choice - which outgoing arrow to take from each mode today (including "do nothing").
• Base case - before day 0 only the start mode is reachable (value 0); every other mode is -infinity.
• Order - left to right over the sequence; compute all of today's modes from yesterday's values.

Say it out loud in the interview:

1. "My modes are ... and here is the diagram." (Draw it - interviewers love this.)
2. "Each arrow gives one max() line; I compute tomorrow from today using temporaries."
3. "The answer is the best among the legal ending modes - you cannot end while still holding."

How it works

For the cooldown problem there are three modes: HOLD (own a share), SOLD (sold today, must rest tomorrow), REST (free, allowed to buy).

flowchart LR
    REST -->|"buy: minus price"| HOLD
    REST -->|"wait"| REST
    HOLD -->|"wait"| HOLD
    HOLD -->|"sell: plus price"| SOLD
    SOLD -->|"forced cooldown"| REST

Trace on prices [1, 2, 3, 0, 2] (start: HOLD = -1 by buying on day 0, SOLD = -inf, REST = 0):

Answer = max(SOLD, REST) on the last day = 3 (buy 1, sell 3, rest, buy 0, sell 2). Note every column uses the previous row's values.

Java template

import java.util.*;

class StateMachineDp {
    static final long NEG = Long.MIN_VALUE / 4;   // "unreachable", safe to add to

    // Generic engine: S modes, one pass over the input.
    static long run(int[] a, int modes, int startMode) {
        long[] cur = new long[modes];
        Arrays.fill(cur, NEG);
        cur[startMode] = 0;                              // base case
        for (int x : a) {
            long[] nxt = new long[modes];
            Arrays.fill(nxt, NEG);
            for (int s = 0; s < modes; s++) {
                if (cur[s] == NEG) continue;
                nxt[s] = Math.max(nxt[s], cur[s]);       // "do nothing" arrow
                // problem-specific arrows, e.g. buy:  nxt[HOLD] = max(nxt[HOLD], cur[FREE] - x)
                //                             sell: nxt[FREE] = max(nxt[FREE], cur[HOLD] + x)
            }
            cur = nxt;                                   // today's values come from yesterday only
        }
        long best = NEG;
        for (long v : cur) best = Math.max(best, v);     // restrict to legal end modes if needed
        return best;
    }

    // Concrete shape: at most k transactions (k = 2 gives Stock III).
    static int maxProfit(int k, int[] prices) {
        int[] hold = new int[k + 1], free = new int[k + 1];
        Arrays.fill(hold, Integer.MIN_VALUE / 2);
        for (int p : prices) {
            for (int j = 1; j <= k; j++) {
                hold[j] = Math.max(hold[j], free[j - 1] - p); // buy opens transaction j
                free[j] = Math.max(free[j], hold[j] + p);     // sell closes transaction j
            }
        }
        return free[k];
    }
}

In maxProfit the in-place update is safe because a same-day buy-then-sell nets zero; when a mode must be blocked for a step (cooldown), keep explicit prev copies instead.

Complexity

• Time: O(n · T) where T is the number of arrows (often a constant like 3-5, or 2k for k transactions).
• Space: O(number of modes) with rolling variables; the full n × modes table is only needed if you must reconstruct the actions.

Variations

• One mode pair, unlimited trades - hold / free. Best Time to Buy and Sell Stock II.
• Cooldown - add a SOLD mode that only leads to REST. Best Time to Buy and Sell Stock with Cooldown.
• Fee - subtract the fee on the sell (or buy) arrow, never both. Best Time to Buy and Sell Stock with Transaction Fee.
• Transaction cap - modes indexed by transaction count. Best Time to Buy and Sell Stock III / IV; if k >= n/2 the cap is irrelevant and it collapses to the unlimited version.
• One-exception budget - modes "exception unused / used". Maximum Subarray Sum with One Deletion.
• Parity / alternation - modes "last pick added / last pick subtracted". Maximum Alternating Subsequence Sum.
• Run-length counting - modes encode "absences so far, current late streak". Student Attendance Record II.

Common mistakes

• Initialising hold to 0 instead of -infinity, which lets you "sell" a share you never bought.
• Counting a transaction on both the buy and the sell arrow - pick one place to increment k.
• Returning max over all modes, including "still holding" - unsold stock is not profit.
• Using Integer.MIN_VALUE as minus infinity and then adding a price - it overflows to a huge positive number.

All practice problems

2 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.