Kadane's Algorithm & Running State

The 10-second versionCopy Anchor Link

Kadane's algorithm finds the maximum sum of a contiguous subarray in a single pass. At every position you keep exactly one number: the best sum of a subarray that ends right here. Either you extend the run you're already carrying, or you throw it away and start fresh at the current element — whichever is bigger. The largest value that running number ever takes is your answer. No nested loops, no tables: one index, one number, O(n).

Why this existedCopy Anchor Link

Here's the part almost nobody knows: Kadane's algorithm wasn't a contest puzzle. It came out of image analysis. The maximum-subarray problem was posed to help estimate the most likely region of a digitized image, and it took a small chain of people to crack.

• 1977 — Ulf Grenander, a statistician at Brown University, poses the problem while working on maximum-likelihood estimation for digitized pictures. He needs the brightest or most "signal-like" contiguous region of a 1D strip, and the harder 2D version.
• 1977 — Michael Shamos answers with a clever divide-and-conquer algorithm running in O(n log n): split the array, recursively solve each half, and handle the subarray that straddles the midpoint.
• Early 1980s — Jay Kadane, at Carnegie Mellon, looks at the problem and finds a startlingly simple O(n) linear-time algorithm — the one we use today.
• 1984 — Jon Bentley retells the whole story in his Programming Pearls column in Communications of the ACM, "Algorithm Design Techniques," which is how the world learned the algorithm — and the name.

Why it mattered: this was one of the first widely-told examples of a problem where the obvious solution is quadratic, the clever solution is O(n log n), and the right solution is a single linear scan with one variable. It became the template for "carry the best state forward," which is the doorway to dynamic programming.

Inside the inventor's headCopy Anchor Link

Look at the problem pattern: given an array of numbers (some negative), find the contiguous run with the largest sum. The straightforward attack examines every possible run:

// try every start and end — O(n^2)function maxSubarrayNaive(a) {  let best = a[0];  for (let i = 0; i < a.length; i++) {    let sum = 0;    for (let j = i; j < a.length; j++) {      sum += a[j];      best = Math.max(best, sum);    }  }  return best;}

That's O(n²) — for each start, extend the end. Shamos beat it with divide and conquer at O(n log n). Impressive, but it still feels like heavy machinery for a problem that reads so simply. So Kadane asks a sharper question: "Do I actually need to remember every start?"

Think about the moment you're standing on element a[i]. Any subarray ending at i either:

1. starts somewhere inside the run you've already been building, or
2. starts exactly at i.

And notice — you don't need to know where a run started, only how good it is so far. If the best-sum-so-far is 5 and the next element is -10, extending gives -5; throwing the run away and starting fresh at -10 gives -10. -5 is bigger, so you extend. But if the run is 5 and the next element is -100, extending gives -95, while starting fresh gives -100… still extend, but the run is now a liability. The instinct is to reset when the carried value drops below just taking the current element alone:

Two things make Kadane's version correct where a careless one isn't:

• The state is "best ending here," not "best so far." That's what lets the recurrence be local: the best run ending at i depends only on the best run ending at i-1. If it depended on the global best, you'd have to remember where the run started, and the elegant collapse would fall apart.
• The all-negative case. A lot of first drafts initialize best = 0, because "an empty subarray sums to 0." But if every element is negative, the true answer is the largest single element (say -1), not 0. Initializing best and cur to a[0] — not zero — is the detail people forget and then fail the edge case.

The final approachCopy Anchor Link

The algorithmCopy Anchor Link

One left-to-right sweep. Maintain cur (best sum ending at the current index) and best (the best cur ever seen).

The invariantCopy Anchor Link

• Definition of cur. After processing index i, cur equals the maximum sum of any subarray that ends at i (and is non-empty).
• Definition of best. After processing index i, best equals the maximum sum over all subarrays ending at any index from 0 to i.
• Recurrence. The best subarray ending at i is either the best ending at i-1 extended by a[i], or a[i] alone — so cur = max(a[i], cur + a[i]). That's the whole algorithm.

Because every subarray ends somewhere, taking the max of cur over all indices covers every subarray exactly once. Nothing is missed and nothing is double-counted.

A worked traceCopy Anchor Link

On [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

Answer: 6, from the subarray [4, -1, 2, 1] (indices 3–6). Watch cur reset at index 1 (from -2 to 1) and index 3 (from -2 to 4) — that's the "reset when it hurts" moment firing.

It in codeCopy Anchor Link

// maximum sum of a non-empty contiguous subarrayfunction maxSubarray(a) {  let best = a[0], cur = a[0];  for (let i = 1; i < a.length; i++) {    cur = Math.max(a[i], cur + a[i]);   // extend or restart    best = Math.max(best, cur);  }  return best;}

Both best and cur start at a[0], which is exactly what makes the all-negative input return the largest (least negative) element instead of 0.

Recovering where the subarray isCopy Anchor Link

If you need the indices, not just the sum, carry one more number: where the current run began, and snapshot it every time cur sets a new record.

function maxSubarrayRange(a) {  let best = a[0], cur = a[0];  let s = 0, bs = 0, be = 0;  for (let i = 1; i < a.length; i++) {    if (a[i] > cur + a[i]) { cur = a[i]; s = i; }   // restart here    else cur += a[i];                                // extend    if (cur > best) { best = cur; bs = s; be = i; }  }  return { best, start: bs, end: be };}

CostCopy Anchor Link

Where you meet it todayCopy Anchor Link

• Finance. The best "buy then later sell" profit over a price series is Kadane's algorithm applied to the differences between consecutive prices.
• Bioinformatics. The maximum-scoring segment of a sequence — scoring aligned fragments of DNA or protein — is the same running-max recurrence, and it's the statistical backbone of BLAST.
• Signal processing. Finding the highest-energy stretch of a signal (the loudest or brightest contiguous window) is maximum subarray over the sample values.
• Streaming analytics. Peak demand over a contiguous period — the busiest few minutes of a server's load — is Kadane computed incrementally as data arrives.

// best profit from one buy followed by a later sellfunction maxProfit(price) {  let best = 0, cur = 0;  for (let i = 1; i < price.length; i++) {    const delta = price[i] - price[i - 1];    cur = Math.max(delta, cur + delta);    best = Math.max(best, cur);  }  return best;}

Here best starts at 0 on purpose: doing no trade is allowed, so the profit never goes negative — the one place a zero start is right instead of wrong.

RecapCopy Anchor Link

• Kadane's algorithm finds the maximum contiguous subarray sum in one pass.
• The state is cur = best sum ending here; the recurrence is cur = max(a[i], cur + a[i]).
• Reset when it hurts: if extending the carried run drags you below a[i], start fresh.
• Initialize best and cur to a[0], not 0, so all-negative inputs return the largest element rather than an empty sum.
• O(n) time, O(1) space — it's the simplest example of carrying one number forward, which is the seed of dynamic programming.

Next up: Binary Search on the Answer — when you can't scan the answer space, but you can test a guess and it only flips one way.