Kadane's Algorithm — Maximum Subarray Sum

What does it solve?

Given an array of integers (positive and negative), find the contiguous subarray that has the largest sum.

The brute-force approach checks all O(n²) subarrays. Kadane's algorithm does it in a single pass — O(n).

The core idea

// At each index, choose the better option:
cur = max(arr[i], cur + arr[i])
// "start fresh" vs "extend current"

best = max(best, cur)
// track the global maximum

Complexity

Time complexity

O(n)

One pass through the array — each element visited exactly once.

Space complexity

O(1)

Only two variables needed: current sum and maximum sum.

Examples & edge cases

Live animation

Current index Best subarray Reset (start fresh)

Current sum

—

Max sum (best)

—

Step

—

Action

—

Select an example and press Play to start.

✓ Complete

Speed Medium

Step-by-step table

Step	Index	Value	cur + val	Current sum	Max sum	Action

C++ implementation

kadane.cpp

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

// Returns {maxSum, startIdx, endIdx}
tuple<int,int,int> kadane(vector<int>& arr) {
    int n = arr.size();
    int cur = arr[0], best = arr[0];
    int curStart = 0, bestStart = 0, bestEnd = 0;
    int tempStart = 0;

    for (int i = 1; i < n; i++) {
        // Decision: start fresh or extend current subarray?
        if (cur + arr[i] < arr[i]) {
            cur = arr[i];       // reset: start fresh from i
            curStart = i;
        } else {
            cur += arr[i];      // extend current subarray
        }

        // Update global maximum
        if (cur > best) {
            best = cur;
            bestStart = curStart;
            bestEnd = i;
        }
    }

    return {best, bestStart, bestEnd};
}

int main() {
    vector<int> arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};

    auto [maxSum, l, r] = kadane(arr);

    cout << "Max subarray sum: " << maxSum << "\n";
    cout << "Subarray: arr[" << l << ".." << r << "]\n";
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars