</>EmbeddedInterview
← All problems · Arrays & Searching

Maximum Subarray Sum (Kadane's Algorithm)

Medium

Implement long max_subarray_sum(const int *a, size_t n) that returns the largest sum of any non-empty contiguous subarray. Run in O(n) time and O(1) memory. Assume n >= 1.

Example: {-2, 1, -3, 4, -1, 2, 1, -5, 4} → 6 (subarray 4, -1, 2, 1).

Write your code on the right and press Run (or Ctrl + Enter). Hidden tests check your functions and print the result below the editor.

For each position, the best subarray ending here either extends the best one ending at the previous position, or starts fresh at this element, whichever is larger. Track the overall best as you go.

#include <stdio.h>
#include <stddef.h>

long max_subarray_sum(const int *a, size_t n)
{
    long long cur = a[0];     /* best sum of a subarray ending at i */
    long long best = a[0];    /* best sum seen anywhere */

    for (size_t i = 1; i < n; i++) {
        long long extend = cur + a[i];
        cur = (extend > a[i]) ? extend : a[i];   /* extend or restart */
        if (cur > best) best = cur;
    }
    return (long)best;
}

Kadane's algorithm is dynamic programming with one variable of state. If the running sum cur becomes negative, carrying it forward can only make later sums smaller, so starting fresh at a[i] is better. That single decision per element gives O(n) time, O(1) memory, versus O(n²) for checking every subarray.

Walk-through: {-2, 1, -3, 4, -1, 2, 1, -5, 4}

i a[i] cur = max(cur + a[i], a[i]) best
0 −2 −2 −2
1 1 max(−1, 1) = 1 1
2 −3 max(−2, −3) = −2 1
3 4 max(2, 4) = 4 4
4 −1 3 4
5 2 5 5
6 1 6 6
7 −5 1 6
8 4 5 6

Edge cases: an all-negative array must return the largest single element, not 0, which is why both variables start at a[0] instead of 0; overflow, handled with a 64-bit accumulator.

Follow-ups: return the start and end indexes (record i when restarting and when best improves); maximum circular subarray (max of Kadane and total − minimum subarray); maximum product subarray (track both max and min because a negative flips them).

solution.c
OutputPress Run to compile and test your code.
Show the hidden tests
/* ---- tests ---- */
static int fails;
#define CHECK(c) do { if (!(c)) { printf("FAIL line %d: %s\n", __LINE__, #c); fails++; } } while (0)
int main(void)
{
    const int a[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
    CHECK(max_subarray_sum(a, 9) == 6);
    const int neg[] = { -8, -3, -6, -2, -5 };
    CHECK(max_subarray_sum(neg, 5) == -2);          /* all negative: best single element */
    const int pos[] = { 1, 2, 3 };
    CHECK(max_subarray_sum(pos, 3) == 6);           /* whole array */
    const int one[] = { -7 };
    CHECK(max_subarray_sum(one, 1) == -7);
    const int mix[] = { 5, -9, 6, -2, 3 };
    CHECK(max_subarray_sum(mix, 5) == 7);           /* 6 - 2 + 3 */
    const int big[] = { 2000000000, 2000000000 };
    CHECK(max_subarray_sum(big, 2) == 4000000000L);
    puts(fails ? "Some tests failed" : "All tests passed");
    return fails != 0;
}