2Brute2Best
🔥0

DP — Kadane / Subarray Pattern: Algorithmic Intuition, Sub-patterns & C++ Guide

For each index, keep the best subarray that ends exactly here: extend the previous one or start fresh.

4 sub-patterns · 11 questions

Remember this · DP — Kadane / Subarray
Trigger
Maximum (or minimum) sum/product of a contiguous subarray, stock buy/sell, circular arrays.
Think
Is the best subarray ending at i either "i alone" or "best ending at i−1, plus i"?
Key question
Should I extend or restart?
A

What is this pattern?

Kadane's idea: for every index i, keep the best subarray that ends exactly at i. That subarray either is a[i] alone (restart) or is the best one ending at i − 1, extended by a[i]. Nothing else is possible.

  • cur = max(a[i], cur + a[i]) — extend or restart.
  • best = max(best, cur) — the answer is the best "ending here" over all i.

One pass, two variables, O(N) time and O(1) space instead of trying all O(N²) subarrays.

The same "carry a small state forward" idea covers more cases:

  • Products: a negative number turns the smallest product into the biggest, so carry both curMax and curMin.
  • Circular arrays: a wrapping subarray is the total minus a middle subarray, so also run a min-Kadane.
  • Stock buy / sell: carry the best profit for each state you can be in at the end of the day (holding a share or free).

Walking along a road collecting coins and paying tolls, with a running purse. If your purse has gone negative, it's better to drop it and start a fresh purse at the next coin — carrying a debt can only make every future total smaller. You also write down the fullest purse you've ever had.

B

See it move

Shaded = the subarray behind cur (the best one ending at i). Gold = the best subarray so far.

Kadane: extend or restartnums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]step 1/10
nums
0
1
2
3
4
5
6
7
8
-2
1
-3
4
-1
2
1
-5
4
▲i
State
cur
-2
best
-2
Start with nums[0]

cur = the best sum of a subarray ending exactly at i. At i = 0 the only choice is [-2], so cur = best = -2 (not 0).

Each column is one day; each row is one state. Purple = values written today from yesterday's column, green = a buy.

Stock states: hold, sold, restprices = [1, 2, 3, 0, 2] (cooldown 1 day)step 1/7
price
0
1
2
3
4
1
2
3
0
2
hold
0
1
2
3
4
sold
0
1
2
3
4
rest
0
1
2
3
4
Before day 0
hold
−∞
sold
−∞
rest
0
Three states

hold = best profit while holding a share; sold = just sold today (tomorrow is a cooldown); rest = free to buy. Before day 0 we can only be free with profit 0.

C

How do I recognise it?

  • "Maximum (or minimum) sum of a contiguous subarray".

  • "Maximum product subarray", or the length of the longest subarray whose product / sign has some property.

  • The array is circular (the end connects to the start).

  • "Buy and sell a stock" — one transaction, unlimited, with cooldown or fee: walk the days and carry the best value for each state.

  • Brute force is "all subarrays" O(N²) and each answer only needs what ends at i.

Looks like DP — Kadane / Subarray, but isn't

Subarray with sum exactly K (or count of them)
→ Prefix Sum + hash map

Kadane finds the best subarray, not one with an exact sum. For exact sums you need earlier prefix sums to look up.

Longest subarray with sum ≤ K, all numbers positive
→ Sliding Window

With a limit to stay under and only positive numbers, a window that grows and shrinks is the tool. Kadane has no limit to respect.

Maximum sum of a subsequence (elements need not be next to each other)
→ DP — 1D (take / skip) or just add the positives

Kadane is only for contiguous pieces. If you may skip elements, the state is "take or skip", not "extend or restart".

Maximum sum subarray of a fixed size k
→ Sliding Window (fixed size)

The length is fixed, so a window of k that slides by one is simpler and exact. (LC 689 combines both: fixed windows plus best-so-far arrays.)

D

How would I discover it from scratch?

Don't memorise “use dp — kadane / subarray”. Ask these questions in order — the pattern falls out.

Try every start l and every end r, and sum a[l..r]: O(N³). Keeping a running sum while r moves gives O(N²).

E

Sub-patterns

Same core idea, different rule for “valid”. Learn them in this order.

01

Maximum subarray

4 questions

The plain Kadane step: the best subarray ending at i is a[i] alone or the one ending at i − 1 extended. Variants flip it to minimum, take the absolute value, or allow one deletion (a second running state).

02

Maximum product

2 questions

Products instead of sums. A negative factor swaps the roles of the largest and smallest product, so both are carried.

03

Circular

1 questions

The best subarray may wrap from the end to the start. A wrapping subarray leaves out a middle piece, so it equals total − (that middle piece); the best wrap removes the minimum subarray.

04

Stock buy / sell

4 questions

Walk the days and keep the best profit for each state you can be in (holding / free / cooling down). Each day's values come from the previous day's.

F

Don't mix these up

Kadane vs Sliding Window

A sliding window needs a rule that says when to shrink (sum too big, a repeat). Kadane has no limit: it restarts whenever the running sum is negative, and negative numbers are allowed.

Kadane vs Prefix Sum

Max subarray can also be written as max(prefix[r] − min prefix before r) — that's Kadane in disguise. Use a prefix-sum hash map only when you need an exact sum or a count.

Max sum subarray vs Max product subarray

For sums one running value is enough. For products a negative can make the smallest value the largest, so carry the min too.

Stock I (one transaction) vs Stock II (unlimited)

One transaction → keep the cheapest price so far. Unlimited → every rising day can be collected; carry hold / free.

G

Code templates (C++)

Kadane (maximum subarray)

Start cur and best at a[0]. Swap max for min for the smallest sum; run both for the largest absolute sum.

kadane-template.cpp
// Kadane: cur = best sum of a subarray that ends exactly here.
// Either a[i] alone (restart) or the best one ending at i - 1, extended.
long long maxSubarray(const vector<int>& a) {
    long long cur = a[0], best = a[0];             // not 0: all-negative arrays need a real answer
    for (size_t i = 1; i < a.size(); i++) {
        cur = max((long long)a[i], cur + a[i]);    // extend or restart
        best = max(best, cur);
    }
    return best;
}

Max and min together (products)

Compute the new curMax and curMin from the old pair, using temporary variables, before overwriting either.

max-product-template.cpp
// Max product subarray: a negative swaps the biggest and smallest product,
// so carry both. A zero resets them (x alone is a candidate).
long long maxProduct(const vector<int>& a) {
    long long curMax = a[0], curMin = a[0], best = a[0];
    for (size_t i = 1; i < a.size(); i++) {
        long long x = a[i];
        long long hi = max({x, x * curMax, x * curMin});   // use the OLD pair for both
        long long lo = min({x, x * curMax, x * curMin});
        curMax = hi; curMin = lo;
        best = max(best, curMax);
    }
    return best;
}

Circular maximum

max(maxKadane, total − minKadane), but if maxKadane < 0 every number is negative and total − minKadane would be the empty subarray — return maxKadane.

circular-template.cpp
// Circular max subarray: either it doesn't wrap (normal Kadane),
// or it wraps = total minus the minimum middle subarray.
int maxCircular(const vector<int>& a) {
    int total = 0, curMax = 0, curMin = 0, bestMax = a[0], bestMin = a[0];
    for (int x : a) {
        curMax = max(x, curMax + x); bestMax = max(bestMax, curMax);
        curMin = min(x, curMin + x); bestMin = min(bestMin, curMin);
        total += x;
    }
    if (bestMax < 0) return bestMax;               // all negative: a wrap would be empty
    return max(bestMax, total - bestMin);
}

Stock states

One variable per state. Read yesterday's values for every update (save them first), and add the rule for the variant: one transaction, cooldown, fee.

stock-template.cpp
// Stock states: carry the best profit for each state at the end of each day.
// Shown with a cooldown (after selling you must rest one day).
int maxProfitStates(const vector<int>& prices) {
    long long hold = LLONG_MIN / 2;   // holding a share
    long long sold = LLONG_MIN / 2;   // sold today (tomorrow is cooldown)
    long long rest = 0;               // free, allowed to buy
    for (int p : prices) {
        long long h = hold, s = sold, r = rest;   // yesterday's values
        hold = max(h, r - p);         // keep holding, or buy today
        sold = h + p;                 // sell what we held
        rest = max(r, s);             // stay free, or yesterday's sale cools down
    }
    return (int)max(rest, sold);
}
// One transaction: keep minPrice so far, profit = max(profit, p - minPrice).
// Unlimited, no cooldown: hold = max(hold, free - p); free = max(free, hold + p).
Next
Start with Maximum subarray