Kadane's Running Best

At a glance

The instinct

Every contiguous subarray ends somewhere. If you know the best subarray that ends at index i - 1, the best one ending at i is either that run extended by a[i], or a[i] on its own. That single choice (extend or restart) is the whole algorithm:

endingHere = max(a[i], endingHere + a[i]) and best = max(best, endingHere).

It is the smallest possible dynamic programme: one state, one transition, no table. The same "best ending here + best overall" idea powers a whole family: products (track max and min), circular arrays (complement trick), and pair scores like Best Sightseeing Pair (carry the best left partner so far).

Recognise it

Not this pattern if...

• You need a subarray with an exact sum or count: use Prefix Sum + hash map.
• There's a length or validity constraint on the window (at most k distinct, size exactly k): use Sliding Window.
• Elements need not be contiguous (subsequence): that's a different DP (e.g. house robber, LIS).
• You need the max subarray sum with a length bound: prefix sums plus a monotonic deque.

Memory hack

Say it out loud in the interview:

1. "State: the best subarray value ending at the current index."
2. "Transition: extend the previous run or restart with just this element."
3. "Answer: the maximum state seen anywhere; initialise with the first element, not zero."

How it works

Trace for Maximum Subarray on [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

The answer 6 comes from [4, -1, 2, 1]; the restart at index 3 happened because the previous run (-2) was dead weight.

Product version: multiplying by a negative swaps "biggest" and "smallest", so keep both maxHere and minHere. When a[i] < 0, swap them before updating. A zero resets both.

Circular version: a wrapping subarray is the whole array minus a non-wrapping middle chunk. So the answer is max(bestMax, total - bestMin), except when every number is negative (then total - bestMin would describe an empty subarray), in which case return bestMax.

flowchart LR
  A["Read a[i]"] --> B{"endingHere + a[i] > a[i] ?"}
  B -- yes --> C["extend: endingHere += a[i]"]
  B -- no --> D["restart: endingHere = a[i]"]
  C --> E["best = max(best, endingHere)"]
  D --> E
  E --> A

Java template

class KadaneToolkit {
    // Classic: best sum of a non-empty contiguous subarray.
    static long maxSubarraySum(int[] a) {
        long endingHere = a[0], best = a[0];             // seed with first element, not 0
        for (int i = 1; i < a.length; i++) {
            endingHere = Math.max(a[i], endingHere + a[i]); // extend or restart
            best = Math.max(best, endingHere);
        }
        return best;
    }

    // Product: track both extremes because a negative flips them.
    static long maxSubarrayProduct(int[] a) {
        long maxHere = a[0], minHere = a[0], best = a[0];
        for (int i = 1; i < a.length; i++) {
            if (a[i] < 0) { long t = maxHere; maxHere = minHere; minHere = t; }
            maxHere = Math.max(a[i], maxHere * a[i]);
            minHere = Math.min(a[i], minHere * a[i]);
            best = Math.max(best, maxHere);
        }
        return best;
    }

    // Circular: either a normal run or total minus the worst run.
    static long maxCircularSum(int[] a) {
        long total = 0, curMax = 0, curMin = 0, bestMax = a[0], bestMin = a[0];
        for (int x : a) {
            curMax = Math.max(x, curMax + x);  bestMax = Math.max(bestMax, curMax);
            curMin = Math.min(x, curMin + x);  bestMin = Math.min(bestMin, curMin);
            total += x;
        }
        return bestMax < 0 ? bestMax : Math.max(bestMax, total - bestMin);
    }

    // Running best partner: maximise left(i) + right(j) for i < j.
    static int bestPairScore(int[] v) {
        int bestLeft = v[0] + 0, best = Integer.MIN_VALUE;
        for (int j = 1; j < v.length; j++) {
            best = Math.max(best, bestLeft + v[j] - j);    // problem-specific right(j)
            bestLeft = Math.max(bestLeft, v[j] + j);       // problem-specific left(j)
        }
        return best;
    }
}

Complexity

• Time O(n): one pass (two quantities per step for product and circular versions).
• Space O(1): a handful of variables; no DP table needed because state i depends only on state i - 1.
• Recovering the actual subarray adds two indices: record a tentative start on every restart and copy it when best improves.

Variations

• Maximum sum: extend or restart. Maximum Subarray.
• Maximum product: keep max and min, swap on negatives, zeros reset. Maximum Product Subarray.
• Circular wrap-around: max(bestMax, total - bestMin) with the all-negative guard. Maximum Sum Circular Subarray.
• Best pair with index penalty: carry the best left score while scanning. Best Sightseeing Pair.
• Differences as the array: Best Time to Buy and Sell Stock is Kadane over price[i] - price[i-1], or equivalently "track min price so far".
• Minimum subarray: same algorithm with min, or negate the input.
• 2D maximum submatrix: fix a pair of rows, collapse columns into sums, run Kadane: O(rows^2 × cols).

Common mistakes

• Initialising best = 0: an all-negative array then wrongly returns 0, which corresponds to an empty subarray the problem usually disallows.
• In the product version, updating maxHere and then using the new value to compute minHere; compute both from the old values (or swap first).
• Forgetting the all-negative guard in the circular version, which returns 0 instead of the largest element.
• Using int for products or long sums that can overflow; widen to long when constraints allow.
• Reaching for a sliding window: with negatives there's no monotone validity rule, so window shrinking has no basis.

All practice problems

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