Kadane's Algorithm
The maximum subarray problem looks like it needs to consider every start and end pair, and it does not. Kadane's insight is that at each position you face exactly one decision — extend the run you are on, or abandon it and start fresh — and the answer to that question only depends on whether the run so far is helping.
This isn't a canned animation. DryRun compiles and executes the code below, then draws every step from the real trace — the same values your machine would produce.
The code
int maxSubarray(vector<int>& a) {
int best = a[0];
int cur = a[0];
for (int i = 1; i < (int)a.size(); i++) {
if (cur + a[i] > a[i]) cur = cur + a[i];
else cur = a[i];
if (cur > best) best = cur;
}
return best;
}
int main() {
vector<int> a = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
cout << maxSubarray(a) << endl;
vector<int> b = {-8, -3, -6, -2, -5};
cout << maxSubarray(b) << endl;
return 0;
}Initialises from a[0] rather than 0, so the all-negative case correctly returns the largest single element (-2 here) instead of 0.
How it works, step by step
cur is the best subarray ending exactly here
Not the best anywhere — the best that finishes at index i. Pinning the definition to end at i is what makes the recurrence work, because a subarray ending at i either includes i-1's run or consists of a[i] alone.
The decision is extend or restart
cur + a[i] versus a[i] compares continuing the previous run against starting over at i. Continuing wins exactly when cur > 0. A negative running total is dead weight: whatever comes next is better off without it.
best is a separate running maximum
cur can and should drop when the array turns negative. best remembers the highest cur ever seen, so a strong early run is not lost when a later stretch of negatives drags cur down.
One pass, no lookahead
The decision at i needs only cur from i-1 and the value a[i]. Nothing about the future is required, which is why a single left-to-right scan suffices and why this is a textbook example of dynamic programming with O(1) state.
Recovering the indices
If you need where the maximum subarray is and not just its sum, track a tentative start that resets whenever cur restarts, and commit it to the answer whenever best updates. Adding this after the fact is where most implementations go wrong, because the start must be recorded at restart time, not at update time.
Complexity
One comparison and one addition per element, with only two integers of state; the brute force is O(n squared) or O(n cubed) because it re-sums ranges that Kadane collapses into a single carried value.
Common bugs
Initialising best and cur to 0
int best = 0 returns 0 for an all-negative array, implicitly claiming the empty subarray is a valid answer. Most problem statements require a non-empty subarray, where the correct answer is the largest single element. Initialise both from a[0] and start the loop at i = 1.
Updating best inside the else branch
Putting the best check only on the extend path misses the case where a single large positive element restarts the run and is itself the maximum. On {-10, 7, -10} you would return -10. The best update belongs after the if/else, unconditionally.
Resetting cur to 0 instead of a[i]
The common if (cur < 0) cur = 0; variant works only if you add a[i] before the check, not after. Mixing the two orderings gives a cur that lags one element behind the window it claims to describe — stepping through and comparing cur against the subarray it is supposed to represent exposes the mismatch immediately.
Reading a[0] from an empty vector
The initialisation dereferences a[0] before any bounds check. An empty input is undefined behaviour rather than a clean error. If empty input is possible, return a sentinel or throw before touching the array.
Each of these is easier to see than to describe — step through it and watch the values change. Run it in DryRun.
Frequently asked
How does Kadane's algorithm work?
It scans the array once, keeping the best sum of a subarray that ends at the current position. At each element it chooses between extending the previous run or starting a new run at that element, whichever is larger, and separately tracks the highest value that quantity has ever reached. That highest value is the maximum subarray sum.
Why does Kadane's algorithm fail on all-negative arrays?
It does not fail if initialised correctly — it fails when best and cur start at 0, because 0 then represents an empty subarray that beats every real one. Initialising both to a[0] and looping from index 1 makes it return the largest single element, which is the correct non-empty answer.
Is Kadane's algorithm dynamic programming?
Yes. The recurrence is cur[i] = max(a[i], cur[i-1] + a[i]), a classic optimal-substructure formulation. Because each state depends only on the immediately previous one, the DP table collapses to a single variable, which is why it looks like a simple loop rather than typical DP.
How do I find the actual subarray, not just the sum?
Keep a tentative start index that resets to i whenever the algorithm restarts the run, and record start and end into the answer only when best is updated. The critical detail is that the tentative start must be set at the moment of the restart, before you know whether that run will win.