Maximum Subarray: Kadane's Algorithm, JavaScript Solution, and Walkthrough
Learn Maximum Subarray with Kadane's JavaScript algorithm, a detailed negative-prefix walkthrough, complexity comparison, and all-negative array pitfalls.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Maximum Subarray asks for the largest sum among contiguous portions of an array. “Contiguous” is the entire challenge: you may not collect every positive number independently. A bad prefix can poison a promising suffix, while a negative number may still belong inside the best run.
Kadane's algorithm makes one decision at each index: extend the best subarray that ended just before this number, or discard that history and start at this number. That local decision works because any negative running sum only makes every future extension worse.
The problem
Given an integer array arr, return the largest possible sum of a non-empty contiguous subarray. The answer is a sum, not the subarray's indices.
Input: arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Explanation: [4, -1, 2, 1] has sum 6The non-empty requirement is important. For [-8, -3, -6], the answer is -3, not zero. An empty subarray is not allowed, so initialize from the first element instead of using a convenient-looking zero.
The brute force baseline
The direct method chooses every start index, grows an end index to the right, and sums each subarray. If it recomputes each sum from scratch, there are O(n²) subarrays and each can take O(n) to add: O(n³).
function maxSubArrayBruteForce(arr) {
let best = -Infinity;
for (let start = 0; start < arr.length; start++) {
for (let end = start; end < arr.length; end++) {
let sum = 0;
for (let i = start; i <= end; i++) sum += arr[i];
best = Math.max(best, sum);
}
}
return best;
}Keeping a running sum inside the nested loops improves that baseline to O(n²), but it still considers far more candidates than necessary. The next index does not need every old subarray; it needs only the best sum that ends immediately before it.
The key insight: abandon a negative prefix
Let currSum mean the maximum subarray sum ending at the previous index. At value arr[i], any valid subarray ending at i has exactly two forms: it is [arr[i]], or it extends that previous best run. Therefore:
best ending at i = max(currSum + arr[i], arr[i])If currSum is negative, adding it to the next value makes that next value smaller. Starting fresh is always at least as good. maxSum separately records the best ending-at-any-index value seen so far, because the answer might have finished long before the array ends.
The optimal solution
The visualizer's canonical implementation is this compact Kadane transition. The order is intentional: update the ending-here state first, then compare its new value with the global best.
function maxSubArray(arr) {
let currSum = arr[0];
let maxSum = arr[0];
for (let i = 1; i < arr.length; i++) {
currSum = Math.max(currSum + arr[i], arr[i]);
maxSum = Math.max(currSum, maxSum);
}
return maxSum;
}There is no special reset statement. Math.max(currSum + arr[i], arr[i]) performs the reset precisely when extending the old run loses to taking the current item alone. Initializing both values with arr[0] also preserves the correct behavior for all-negative arrays.
Walkthrough: [-2, 1, -3, 4, -1, 2, 1]
| i | arr[i] | Previous currSum | max(previous + value, value) | New currSum | maxSum |
|---|---|---|---|---|---|
| 0 | -2 | — | initialize | -2 | -2 |
| 1 | 1 | -2 | max(-1, 1) | 1 | 1 |
| 2 | -3 | 1 | max(-2, -3) | -2 | 1 |
| 3 | 4 | -2 | max(2, 4) | 4 | 4 |
| 4 | -1 | 4 | max(3, -1) | 3 | 4 |
| 5 | 2 | 3 | max(5, 2) | 5 | 5 |
| 6 | 1 | 5 | max(6, 1) | 6 | 6 |
At index 1, retaining -2 would produce -1; the algorithm starts at 1. At index 3, retaining the -2 from index 2 would produce only 2, so it starts at 4. Later, the small negative -1 is worth keeping because the running sum stays positive and the next values lift it to 6.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Triple-loop brute force | O(n³) | O(1) | recomputes every candidate sum |
| Running-sum nested loops | O(n²) | O(1) | enumerates every start and end pair |
| Kadane's algorithm | O(n) | O(1) | one constant-time transition per element |
Kadane's algorithm is a dynamic-programming compression: a full dp[i] array of best sums ending at i would be correct, but only dp[i - 1] is needed to compute the next state. currSum is that one retained cell.
The recurrence also gives a compact proof. Assume currSum is the best sum among all subarrays ending at i - 1. Any subarray ending at i either contains that previous position, in which case the best candidate is currSum + arr[i], or begins at i, in which case it equals arr[i]. Taking the larger establishes the invariant for the next iteration; recording the largest invariant value establishes the global answer.
Common mistakes
- Starting
currSumat zero. This returns 0 for an all-negative array even though the problem requires a non-empty subarray. - Using
maxSumin the recurrence. Extend onlycurrSum, which represents a subarray ending next to the current value. The global best may end somewhere else and cannot be extended contiguously. - Updating
maxSumbeforecurrSum. That compares yesterday's ending-here value and can miss a record made at the current index. - Dropping every negative number. A negative value can remain in the optimal subarray when the sum before it is large enough.
- Returning indices from a sum-only implementation. This version tracks values only; index recovery needs start and best-boundary bookkeeping.
Where this pattern shows up next
- Min Cost Climbing Stairs compresses a recurrence to the state needed for the next step.
- House Robber repeatedly chooses between extending a compatible history and skipping it.
- House Robber II adds a circular boundary constraint to that choice.
- Coin Change uses dynamic-programming states to avoid recomputing overlapping decisions.
You can also step through it interactively and watch each negative prefix be rejected or retained.
FAQ
Why does Kadane's algorithm discard a negative running sum?
For any future value x, negativeSum + x is smaller than x. A negative prefix can never improve a subarray that must end in the future, so starting at the new value is always better.
Does Maximum Subarray work when every number is negative?
Yes, provided currSum and maxSum begin at the first element. The recurrence then selects the least-negative single element, which is the maximum non-empty contiguous sum.
What is the difference between currSum and maxSum?
currSum is the best sum for a subarray that must end at the current index. maxSum is the best result anywhere in the processed prefix. Keeping them separate preserves contiguity and the global answer.
Can Kadane's algorithm return the subarray itself?
Yes, with extra index tracking. When the recurrence chooses arr[i] instead of extending, record a new tentative start; whenever maxSum improves, save that start and the current index. The sum recurrence remains unchanged.
What test cases expose Maximum Subarray bugs?
Use a one-item array, an all-negative array such as [-8, -3, -6], and a case that resets after a negative prefix like [-2, 1]. Then test a winning run containing a negative value, such as [4, -1, 2, 1], to ensure the implementation does not discard numbers merely because they are negative.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.