Kadane's Algorithm

Dynamic Programming O(n) O(1)

Maximum subarray sum in one pass: extend the running sum while it helps, restart at the current element when it turns negative.

cur = best subarray sum ending at each value

a	-2	1	-3	4	-1	2	1	-5	4
cur	-2	·	·	·	·	·	·	·	·

Sequence

1/22

Start: best = cur = a[0] = -2.

Invariantcur is the largest sum of a run ending exactly at i; best is the largest seen anywhere.

computingreads fromfilled

kadane.c

int kadane(int a[], int n) {
    int best = a[0];
    int cur = a[0];
    for (int i = 1; i < n; i++) {
        if (cur + a[i] > a[i])
            cur = cur + a[i];   /* extend the run   */
        else
            cur = a[i];         /* restart run here */
        if (cur > best)
            best = cur;
    }
    return best;
}

How Kadane's Algorithm works

Walk the array once keeping the best sum that ends here: either extend the running sum or restart at the current element if the running sum went negative — a negative prefix can never help.

Best case

Always one pass: O(n), O(1) space.

Worst case

All-negative arrays still work — the answer is the largest single element.

When to use it

Maximum subarray sum: best trading window, brightest image strip, 1-D profit runs.