Maximum Subarray

Problem. Find the contiguous subarray with the largest sum.

Kadane’s algorithm — $O(n)$

long long maxSubarray(const vector<long long>& a) {
    long long best = a[0], cur = 0;
    for (long long x : a) {
        cur = max(x, cur + x);                    // extend, or start fresh here
        best = max(best, cur);
    }
    return best;
}

cur is the best sum of a subarray ending at the current index. Either extend the previous one or start over — whichever is larger. See Kadane’s Algorithm.

All-negative arrays

Initialising best = 0 returns 0 for an all-negative array. If the subarray must be non-empty, initialise best = a[0] as above. Read the statement.

The prefix-sum view

${\max }_{l\le r}\mathrm{sum}(l,r)={\max }_r(\mathrm{pref}[r]-{\min }_{l\le r}\mathrm{pref}[l]).$

Track the running minimum prefix. Equivalent to Kadane, but it generalises better — length constraints, “at most $k$ elements”, and range queries all follow from this form.

long long best = LLONG_MIN, minPref = 0, pref = 0;
for (long long x : a) {
    pref += x;
    best = max(best, pref - minPref);
    minPref = min(minPref, pref);
}

The variants

Variant	Method
Maximum sum	Kadane
Circular maximum sum	$\max (\text{Kadane},\text{total}-\text{minSubarray})$ — with an all-negative guard
Maximum product	track both max and min ending here (negatives flip)
Length exactly $k$	sliding window
Length at least $k$	prefix sums + running minimum with a lag
Length at most $k$	prefix sums + monotonic deque
Sum $\le K$, maximise	prefix sums + a set and lower_bound, $O(n\log n)$
Maximum average, length $\ge L$	binary search the average, subtract, look for a positive sum
$k$ disjoint subarrays	DP, $O(nk)$
2D maximum sum submatrix	fix the row pair, collapse to 1D, apply Kadane — $O(n^{2}m)$
Return the indices	track where cur was reset
With updates	segment tree storing (total, best prefix, best suffix, best)

Circular maximum subarray

Either the answer does not wrap (plain Kadane), or it wraps — in which case the unused middle part is a minimum subarray:

long long circularMax(vector<long long>& a) {
    long long total = accumulate(a.begin(), a.end(), 0LL);
    long long maxK = kadaneMax(a), minK = kadaneMin(a);
    if (minK == total) return maxK;               // all negative: wrapping is empty
    return max(maxK, total - minK);
}

The guard matters: if every element is negative, total - minK is the empty subarray.

2D maximum submatrix

for (int top = 0; top < n; top++) {
    vector<long long> col(m, 0);
    for (int bot = top; bot < n; bot++) {
        for (int j = 0; j < m; j++) col[j] += g[bot][j];
        best = max(best, kadane(col));            // 1D on the collapsed columns
    }
}

$O(n^{2}m)$. The “fix a row pair, collapse, apply the 1D solution” pattern extends many 1D array algorithms to 2D.

Segment tree node — for the query version

struct Node { long long total, pre, suf, best; };
Node merge(Node a, Node b) {
    return { a.total + b.total,
             max(a.pre, a.total + b.pre),
             max(b.suf, b.total + a.suf),
             max({a.best, b.best, a.suf + b.pre}) };
}

Four values per node make “maximum subarray sum in a range, with point updates” an $O(\log n)$ query. This is the standard example of a richer segment tree node, and the merge is worth memorising.

Why it is worth knowing

Kadane is the smallest non-trivial DP: one state, one transition, $O(1)$ space. It is the cleanest illustration that a DP’s state can be “the best answer ending here” rather than “the best answer so far” — a reframing that unlocks a great many sequence problems.

See also: Kadane’s Algorithm · Prefix Sum · Segment Tree