Kadane & Running-State DP

Kadane's algorithm finds the maximum-sum contiguous subarray in one $O(n)$ pass with $O(1)$ space. At each index you keep "the best sum of a subarray that ends here" and a global best. The same skeleton, with one or two extra state variables, solves circular sums, products, one-deletion and alternating variants.

The idea: baggage vs fresh start#

Every Kadane problem comes down to one decision at index i: is the history so far useful, or is it a burden?

Extend: current + nums[i]. The history is positive, so keep it.
Restart: nums[i]. The history is negative baggage, so drop it and start fresh here.

current = max(current + x, x) makes that choice, and best = max(best, current) remembers the best ending anywhere. It's correct because any best subarray ending at i is either nums[i] alone or the best subarray ending at i - 1 plus nums[i]; nothing else can be better.

One rule holds for every variant: you never look back more than one step. Your whole history is compressed into a few variables (current, no_del, up, and so on). That makes Kadane a tiny DP where the table has been squeezed down to its last row.

How to spot it#

Kadane is easy to confuse with sliding windows and general DP, so ask these questions when you see a subarray or subsequence problem.

Contiguous? If yes, it's likely Kadane or a sliding window.
Can negatives break the greedy? If so, also track min_so_far, or take abs.
Is there a one-time special move (delete, square, swap one element)? You need two states: clean and dirty.
Does the sign alternate (+ - + -)? You need two states: peak and valley.

The moment you may pick elements freely (non-contiguous), Kadane breaks, and you're in general Dynamic Programming or Greedy territory.

Template#

Plain Kadane is the extend-or-restart choice in a loop. It keeps two numbers: the best sum ending here and the best anywhere.

current = best = items[0]        # not 0: all-negative arrays exist
for each x in items after the first:
    current = max(current + x, x)    # extend the baggage or start fresh
    best = max(best, current)
return best

To also return where the best subarray is, keep a temp_start. Reset it to i + 1 whenever the running sum drops below zero, and copy it into best_start whenever best improves.

Questions 2 to 4 above each call for a second state. The shape stays the same, but each new state reads only the old values from the previous step.

state_a = state_b = starting values
best = items[0]
for each x in items after the first:
    old_a, old_b = state_a, state_b      # snapshot before updating
    state_a = best of (extend old_a with x, restart at x)
    state_b = best of (extend old_b with x, switch from old_a with x)
    best = max(best, state_a, state_b)
return best

The three meta-patterns#

The two-state template is generic on purpose. Most variants fit one of three shapes, and each one changes what the two states mean.

The mirror: track max and min together#

The best result may come from the worst history. Run a "max ending here" and a "min ending here" side by side. Use it for circular sums, products and absolute sums.

The coupon: two timelines#

You hold a token you can spend once (delete one element, square one element). Keep two timelines: clean (no coupon used) is standard Kadane, and dirty (coupon used) is the other.

$\text{dirty} = \max(\text{dirty} + x,\ \text{clean}_{\text{prev}} + \text{special}(x))$

The dirty timeline can also start fresh at the current index, with the coupon spent right away. That case is easy to miss.

The ping-pong: alternating states#

The sign of each step alternates (+ - + -). up depends on the previous down, and down on the previous up. The question is the same as always: start from scratch here, or carry over the opposite run?

Trace: why the snapshot matters#

The "snapshot before updating" line in the template is the step people skip, and the mirror pattern shows why it matters. For maximum product, the update for lo needs the old hi. Here is nums = [-1, -2, -9, -6] done right, next to a version whose lo update leaves out old_hi * x:

x	hi	lo	best	lo without `old_hi * x`
-1	-1	-1	-1	-1
-2	2	-2	2	-2
-9	18	-18	18	-9
-6	108	-108	108	-6

At x = -9 the old maximum 2 should flip into the new minimum 2 × -9 = -18. Leaving out that term makes lo = -9, so on the next step the best product is 54 instead of 108.

Pitfalls#

These are the mistakes that most often cost a correct answer.

Updating with already-updated values. In the mirror and ping-pong patterns, snapshot the old values (prev_hi = hi) before updating, or update both with a tuple assignment.
The empty-subarray trap. A formula built from the total can quietly pick an empty subarray. Check the all-negative input.
Starting best at 0. For an all-negative array the answer is the largest single element, not 0. Start from nums[0].
Forgetting "start the op here". In coupon problems the dirty state can also begin at the current index.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with Maximum Subarray.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Maximum Subarray

This is plain Kadane. Start current and best at nums[0], not 0.

Hint: Maximum Sum Circular Subarray

A wrapping subarray is the total minus a non-wrapping subarray. So the answer is max(max_sub, total - min_sub), with Kadane for the minimum run alongside the maximum. If every number is negative, total - min_sub is the empty subarray, so return max_sub when max_sub < 0.

Hint: Maximum Product Subarray

A negative times a negative is a big positive. Track the largest and the smallest product ending here. Multiplying by a negative swaps their roles, so snapshot both before you update.

Hint: Maximum Absolute Sum of Any Subarray

Run Kadane for the maximum and for the minimum. The answer is max(max_sub, abs(min_sub)).

Hint: Maximum Subarray Sum with One Deletion

The coupon is one deletion. The clean state is plain Kadane. The dirty state either used the coupon earlier and adds x, or deletes x now and keeps the old clean value: one_del = max(one_del + x, prev_no_del).

Hint: Maximum Subarray Sum After One Operation

The coupon is squaring one element. The dirty state is the larger of dirty + x and clean_prev + x * x. Also try x * x alone: start a new subarray here and spend the coupon right away.

Hint: Longest Turbulent Subarray

Keep up and down run lengths. If arr[i] > arr[i-1], the new up is the old down + 1 and down resets to 1. Mirror that for a decrease, and reset both on equality.

Hint: Maximum Alternating Subsequence Sum

It uses the same up/down pair, but on a subsequence. So it is a state-machine DP, not contiguous Kadane: each state may also skip the current element.

Hint: Best Time to Buy and Sell Stock

Carry one piece of running state: the cheapest price so far. At each day, the best sale ending today is price - cheapest. Keep the maximum.

Key takeaways#

At every index ask: is the history baggage or a head start? max(current + x, x).
You never look back more than one step; the history lives in a few variables.
Mirror: track max and min together when the worst history can become the best.
Coupon: keep a clean and a dirty timeline, and snapshot the clean one before updating.
Ping-pong: alternate states feed each other; use temporaries so you read the old values.

Core idea#

At each index, decide to extend the best subarray that ends here or restart at the current element. Keep a global best. One pass, $O(n)$ time, $O(1)$ space.

Key points#

current = max(current + x, x): is the history useful, or negative baggage?
The best subarray ending at i is nums[i] alone, or the best ending at i - 1 plus nums[i].
Never look back more than one step. The history lives in a few variables.
Contiguous? Kadane or a sliding window. Free picks? General DP or greedy.

Three meta-patterns#

Pattern	Use for	States
Mirror	Circular sum, max product, max absolute sum	max and min ending here
Coupon	One deletion, one squaring	clean and dirty timelines
Ping-pong	Turbulent subarray, alternating subsequence sum	`up` and `down`

Circular: max(max_sub, total - min_sub). Return max_sub when max_sub < 0.
Product: multiplying by a negative swaps the max and the min.
Absolute sum: max(max_sub, abs(min_sub)).
Coupon: dirty = max(dirty + x, clean_prev + special(x)). For squaring, also try x * x alone.

Template#

clean = best = items[0]
dirty = minus infinity           # coupon used
for each x in items after the first:
    old_clean = clean            # snapshot the clean state first
    clean = max(clean + x, x)
    dirty = max(dirty + x, old_clean + special(x))
    best = max(best, clean, dirty)
return best

Plain Kadane is the clean line alone. For one deletion, special(x) adds nothing.

Pitfalls#

Updating with already-updated values. Snapshot old values, or use a tuple assignment.
The all-negative circular case. total - min_sub is the empty subarray.
Starting best at 0. Start from nums[0].
Forgetting that the dirty state can begin at the current index.

Say it in an interview#

"At every index, either extend the history or start fresh: max(current + x, x)."
"For products, track the max and the min, because a negative flips them."