Kadane's Algorithm — Maximum Subarray Sum

What does it solve?

Find the contiguous subarray with the largest sum. Checking every subarray is O(N²); Kadane's does it in one pass by turning it into a tiny dynamic program.

Key insight: let cur be the best subarray sum ending at i. Either extend the previous run (cur + a[i]) or start over at a[i], whichever is larger. If the running sum ever goes negative it can only hurt what follows, so drop it and restart. Keep best = max of all cur → O(N) time, O(1) space.

The core idea

// cur = best sum ending at i
cur = a[0], best = a[0]
for i in 1..n-1:
cur = max(a[i], cur + a[i])
best = max(best, cur)
return best

Complexity

Time complexity

O(N)

One left-to-right pass, doing constant work per element: two comparisons and two updates.

Space complexity

O(1)

Just cur and best (plus optional start/end indices to recover the subarray). No DP table.

Examples & edge cases

Live animation — extend or restart, track the best run

current element in current run restart (drop run) best subarray

Values (positive up, negative down)

Press Play to begin…

Current decision

i = — cur = — best = — range = —

Step — of —

nums[i]

—

current value

cur (ends at i)

—

running sum

best so far

—

max subarray

decision

—

extend / restart

Select an example and press Play to start.

✓ Done

Speed Medium

Step-by-step table

Step	i	nums[i]	cur+a[i]	decision	cur	best	range

C++ implementation

kadanes_algorithm.cpp

#include <bits/stdc++.h>
using namespace std;

// Maximum contiguous subarray sum (Kadane's)
int maxSubArray(vector<int>& a) {
    int cur = a[0], best = a[0];

    for (int i = 1; i < (int)a.size(); i++) {
        // extend the run, or start fresh at a[i]
        cur = max(a[i], cur + a[i]);
        best = max(best, cur);
    }
    return best;
}

// Variant that also recovers the subarray [lo, hi]
int maxSubArrayRange(vector<int>& a, int& lo, int& hi) {
    int cur = a[0], best = a[0], start = 0;
    lo = hi = 0;
    for (int i = 1; i < (int)a.size(); i++) {
        if (a[i] > cur + a[i]) { cur = a[i]; start = i; } // restart
        else cur += a[i];                                // extend
        if (cur > best) { best = cur; lo = start; hi = i; }
    }
    return best;
}

int main() {
    vector<int> a = {-2,1,-3,4,-1,2,1,-5,4};
    cout << maxSubArray(a) << "\n"; // 6  ([4,-1,2,1])
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars