Linear DP

What is this?

Walk along a row of choices, and at each step ask: what is the best answer that ends here? Not "the best answer overall" — that comes later, by taking the best of all the endings. Restricting the question to "ending exactly here" is what makes the recurrence local, because the only thing you need is the answer that ended at the previous position.

Once the state is defined that way, all four problems in this chapter are one line of arithmetic apiece.

💡 Fun fact: Maximum Product Subarray is the problem that breaks the habit built by every other one in this chapter. With sums, the running maximum is all you need. With products, multiplying by a negative swaps the roles of the largest and smallest — so the most negative running value is a candidate for the next maximum. Tracking max alone silently fails on [-2, 3, -4], whose answer is 24 and which no single-variable version will find.

🔓 The 4 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: define dp[i] as the answer ending at i, not the answer so far. That makes the recurrence depend on a couple of neighbours, and the overall answer becomes a maximum (or a sum) over the finished table.

1. Four recurrences

The Kadane recurrence is worth reading closely: max(nums[i], dp[i-1] + nums[i]) is exactly the question "is the run so far helping me, or should I start fresh here?" If dp[i-1] is negative, dragging it along can only hurt, so you restart.

2. When one value is not enough

best = cur_max = cur_min = nums[0]
for x in nums[1:]:
    if x < 0:
        cur_max, cur_min = cur_min, cur_max     # a negative swaps the roles
    cur_max = max(x, cur_max * x)
    cur_min = min(x, cur_min * x)
    best = max(best, cur_max)

The swap is the entire trick. Multiplying by a negative turns the most negative running product into the largest, so both must be carried and exchanged whenever the incoming value is negative.

3. Decode Ways is a counting DP

Rather than a maximum, dp[i] counts the ways to decode the first i characters. Two ways to arrive: take the last character alone if it is 1–9, or take the last two together if they form 10–26. Add the counts. The base case dp[0] = 1 represents the empty string having exactly one decoding, which is the identity for a product of counts rather than an arbitrary choice.

4. A 30-second worked example (Max Product)

nums = [-2, 3, -4]

start:   cur_max = cur_min = best = -2

x = 3    (positive, no swap)
         cur_max = max(3, -2 x 3)  = max(3, -6)  = 3
         cur_min = min(3, -2 x 3)  = min(3, -6)  = -6
         best = 3

x = -4   (negative → SWAP: cur_max = -6, cur_min = 3)
         cur_max = max(-4, -6 x -4) = max(-4, 24) = 24  ✅
         cur_min = min(-4,  3 x -4) = min(-4, -12) = -12
         best = 24

The answer 24 comes from the whole array -2 × 3 × -4, and it was found only because -6 was still being carried when the -4 arrived.

5. Where you'll actually meet this

• Time-series analysis. Best-performing contiguous window of returns is Kadane, applied daily in finance.
• Signal processing. Maximum-energy segment of a waveform.
• Scheduling with exclusions. House Robber's "cannot take adjacent" is the shape of any non-adjacent selection problem.
• Encoding and parsing. Counting valid interpretations of an ambiguous string is Decode Ways — the same structure as counting parses in a grammar.
• Anomaly detection. Longest stretch whose aggregate exceeds a threshold.

6. Problems in this chapter

▶ Maximum Subarray Sum

Largest sum of a contiguous subarray. Kadane: extend the run or restart at the current element.
Pattern: best-ending-here. Target: O(n) time, O(1) space.

▶ House Robber

Maximum total from non-adjacent houses. Take this house plus dp[i-2], or skip it and keep dp[i-1].
Pattern: take-or-skip with a gap. Target: O(n) time, O(1) space with two rolling variables.

▶ Decode Ways

Count the ways a digit string maps to letters. Add the one-digit and two-digit continuations, respecting the 10–26 range and the leading-zero rule.
Pattern: counting DP with validity checks. Target: O(n) time, O(1) space.

▶ Maximum Product Subarray

Largest product of a contiguous subarray. Track both the running maximum and minimum, swapping them on a negative.
Pattern: dual-state linear DP. Target: O(n) time, O(1) space.

7. Common pitfalls 🚫

• Tracking only the maximum for products. [-2, 3, -4] returns 3 instead of 24.
• Initialising best to zero. For an all-negative array the answer is the least negative element, not 0.
• Forgetting zeros in the product problem. A zero resets both running values; max(x, cur * x) handles it naturally, which is why the max with the bare element matters.
• Mishandling leading zeros in Decode Ways. "0" decodes zero ways, and "06" is not a valid two-digit code.
• Base case dp[0] = 0 for a counting DP. It must be 1 — the empty string has one decoding.
• Returning dp[n-1] for Kadane. The answer is the maximum over all dp[i], not the last one.
• Writing the array when two variables suffice. Correct, and the follow-up is always "now in O(1) space".

8. Key takeaways

1. Define dp[i] as "ending at i". Local endings make local recurrences.
2. Extend or restart is the whole of Kadane, and the question it asks is whether the past is helping.
3. Products need two running values, exchanged whenever a negative arrives.
4. Counting DPs use 1 as the empty-input base case, because it is the identity.
5. The answer is often a maximum over the table, not its last entry.
6. Roll the array into variables — every problem here is O(1) space.
7. Why interviewers like it: the recurrences are short enough to write in two minutes, so the conversation is about your state definition and your edge cases.

Order: Maximum Subarray Sum → House Robber → Decode Ways → Maximum Product Subarray.