Kadane's Algorithm: Maximum Subarray Sum Explained

Quick Answer

Kadane's Algorithm finds the maximum sum of any contiguous subarray in a single O(n) pass. At every index it decides whether extending the current run is still worth it, or whether the run so far is dragging the total down enough that starting fresh from here beats keeping it. It tracks a running current sum and a separate best seen so far, updating both while scanning left to right.

The Problem: Every Subarray Has a Sum — Which One Is Biggest?

Given an array of numbers, find the contiguous subarray (at least one element) with the largest sum. Contiguous is the whole point — you cannot skip elements and cherry-pick the biggest ones; they have to sit next to each other in the original array. This shows up constantly in disguise: "longest profitable stretch," "best consecutive run of scores," "the worst losing streak," all reduce to the same shape.

The obvious way to solve it is to check every possible subarray, add up its elements, and keep the biggest total seen so far:

function maxSubArrayBrute(nums) {
  let best = -Infinity;
  for (let i = 0; i < nums.length; i++) {
    let sum = 0;
    for (let j = i; j < nums.length; j++) {
      sum += nums[j];
      best = Math.max(best, sum);
    }
  }
  return best;
}

This works and it is easy to reason about, but it is O(n²) — for every starting index i it walks every possible ending index j. For a small array of 9 elements that's 45 additions, no big deal. For a real dataset of 100,000 daily price changes, that's roughly 5 billion additions. It needs to be one pass, not nested loops.

The Insight: A Negative Running Sum Is Dead Weight

Walk the array left to right and track a running sum — call it current — for the best subarray that ends at the position you're standing on. At each step there are only two options: extend the previous run by adding the new number to it, or abandon everything before this point and start a brand new subarray right here.

Extending only ever pays off if current, before adding the new number, is positive — adding a positive amount to the new number gives you more than the new number alone would. The moment current has gone negative, it is actively subtracting from whatever comes next, so cut it loose and restart. That single decision, repeated once per element, is the entire algorithm:

current = Math.max(nums[i], current + nums[i]);

Either the new element on its own beats extending the old run, or extending still wins — there is no third option, and no need to look further back than the immediately preceding step. That is what collapses an O(n²) search into a single O(n) pass: at each index, the entire history that matters is already summarized in one number.

Kadane's Algorithm, Step by Step

Turning that decision into code:

function maxSubArray(nums) {
  let best = nums[0];
  let current = nums[0];
  for (let i = 1; i < nums.length; i++) {
    current = Math.max(nums[i], current + nums[i]);
    best = Math.max(best, current);
  }
  return best;
}

Tracing it against [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

i    num   current   best
0    -2    -2        -2
1     1     1         1
2    -3    -2         1
3     4     4         4
4    -1     3         4
5     2     5         5
6     1     6         6
7    -5     1         6
8     4     5         6

The answer is 6, coming from the subarray [4, -1, 2, 1]. Notice what happens at i=2: current goes to -2, which is worse than the standalone value -3 would suggest — but it's still better than throwing away the 1 before it, since -2 > -3. The algorithm doesn't discard a run just because it went negative overall in one step; it discards it only when continuing to carry it forward would cost more than starting fresh, which the Math.max comparison checks fresh at every single index.

The Gotcha: Initializing best to 0 Breaks All-Negative Arrays

The most common bug with Kadane's algorithm isn't in the recurrence — it's in the seed values. A tempting shortcut is to initialize best = 0 and current = 0, on the reasoning that "the empty subarray sums to 0, so 0 is a safe floor." That reasoning is wrong for this problem: a subarray must contain at least one element, so when every number in the array is negative, the correct answer is the least-negative single element — not 0, which no subarray actually sums to.

function maxSubArrayBuggy(nums) {
  let best = 0;     // wrong seed
  let current = 0;
  for (let i = 0; i < nums.length; i++) {
    current = Math.max(nums[i], current + nums[i]);
    best = Math.max(best, current);
  }
  return best;
}

maxSubArray([-3, -1, -2, -4]);       // -1  (correct)
maxSubArrayBuggy([-3, -1, -2, -4]);  // 0   (wrong — no subarray here sums to 0)

Both versions were run against the same input to confirm this: the correct version returns -1, matching a brute-force check; the buggy version returns 0, a number that cannot possibly be right since every element is negative. The fix is simply to seed both trackers with nums[0] and start the loop from index 1, exactly as in the correct version above — never seed either one with a bare 0.

Bonus: Returning the Actual Subarray, Not Just the Sum

Interview questions and real use cases often want more than a number — they want to know which subarray produced it, so it can be highlighted, logged, or acted on. That means tracking a couple of extra index variables alongside the sums:

function maxSubArrayWithIndices(nums) {
  let best = nums[0];
  let current = nums[0];
  let start = 0, end = 0, tempStart = 0;
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] > current + nums[i]) {
      current = nums[i];
      tempStart = i;
    } else {
      current = current + nums[i];
    }
    if (current > best) {
      best = current;
      start = tempStart;
      end = i;
    }
  }
  return { sum: best, subarray: nums.slice(start, end + 1) };
}

maxSubArrayWithIndices([-2, 1, -3, 4, -1, 2, 1, -5, 4]);
// { sum: 6, subarray: [4, -1, 2, 1] }

tempStart marks where the current candidate run began; it only gets promoted to the recorded start when that run actually produces a new best sum. This separation matters — a run can restart several times before finally becoming the winning one, and only the winning run's start should be kept.

Where Kadane's Algorithm Shows Up

The most direct relative is Best Time to Buy and Sell Stock: convert a list of prices into day-over-day differences, then run Kadane's algorithm on those differences — the maximum subarray sum of the differences is exactly the maximum profit from one buy and one sell. It's the same algorithm wearing a different problem statement.

A common extension is maximum sum circular subarray, where the array wraps around from the last element back to the first. The trick: compute the normal Kadane's maximum, then separately compute the minimum subarray sum and subtract it from the total array sum — that gives the best wrap-around subarray, and the answer is whichever of the two is larger.

It also appears inside bigger algorithms: the 2D version, maximum sum rectangle in a matrix, fixes a pair of column boundaries, collapses each row into a single column-sum array, and runs 1D Kadane's on that — turning an O(n⁴) brute force over a grid into something practical. Recognizing the shape — "contiguous run, one running decision per step" — is what makes Kadane's one of the most transferable patterns in an interview toolkit, well beyond the exact problem it was named for.

Frequently Asked Questions