Kadane's Algorithm Maximum Subarray in DSA C

Mental Model

Find the biggest sum of any continuous part of a list by keeping track of the best sum ending at each position.

Analogy: Imagine walking along a path with ups and downs in height. You want to find the highest hill segment you can climb without stopping. You keep track of the best climb you can make ending at each step.

Array: [ -2, 1, -3, 4, -1, 2, 1, -5, 4 ]
Index:  0   1   2   3   4   5   6   7   8

At each step:
max_ending_here -> current best sum ending here
max_so_far    -> best sum found so far

Dry Run Walkthrough

Input: array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Goal: Find the maximum sum of any continuous subarray

Step 1: Start with first element: max_ending_here = max_so_far = -2

max_ending_here = -2, max_so_far = -2

Why: Initialize with first element to start tracking sums

Step 2: Move to element 1: max_ending_here = max(1, -2 + 1) = 1; max_so_far = max(-2, 1) = 1

max_ending_here = 1, max_so_far = 1

Why: Either start new subarray at current element or extend previous

Step 3: Element 2: max_ending_here = max(-3, 1 + -3) = -2; max_so_far = max(1, -2) = 1

max_ending_here = -2, max_so_far = 1

Why: Current element lowers sum, so start new subarray or keep previous max

Step 4: Element 3: max_ending_here = max(4, -2 + 4) = 4; max_so_far = max(1, 4) = 4

max_ending_here = 4, max_so_far = 4

Why: Better to start new subarray at 4 than continue negative sum

Step 5: Element 4: max_ending_here = max(-1, 4 + -1) = 3; max_so_far = max(4, 3) = 4

max_ending_here = 3, max_so_far = 4

Why: Extend current subarray even if sum decreases, still better than previous max

Step 6: Element 5: max_ending_here = max(2, 3 + 2) = 5; max_so_far = max(4, 5) = 5

max_ending_here = 5, max_so_far = 5

Why: Sum increases, update max_so_far

Step 7: Element 6: max_ending_here = max(1, 5 + 1) = 6; max_so_far = max(5, 6) = 6

max_ending_here = 6, max_so_far = 6

Why: Keep extending subarray to get bigger sum

Step 8: Element 7: max_ending_here = max(-5, 6 + -5) = 1; max_so_far = max(6, 1) = 6

max_ending_here = 1, max_so_far = 6

Why: Sum drops, but max_so_far stays the same

Step 9: Element 8: max_ending_here = max(4, 1 + 4) = 5; max_so_far = max(6, 5) = 6

max_ending_here = 5, max_so_far = 6

Why: Sum improves but not better than max_so_far

Result:

max_so_far = 6
Maximum subarray sum is 6

Annotated Code

DSA C

#include <stdio.h>

int max(int a, int b) {
    return (a > b) ? a : b;
}

int kadane(int arr[], int n) {
    int max_ending_here = arr[0];
    int max_so_far = arr[0];

    for (int i = 1; i < n; i++) {
        max_ending_here = max(arr[i], max_ending_here + arr[i]); // update max_ending_here
        max_so_far = max(max_so_far, max_ending_here);          // update max_so_far
    }

    return max_so_far;
}

int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int max_sum = kadane(arr, n);
    printf("Maximum subarray sum is %d\n", max_sum);
    return 0;
}

max_ending_here = max(arr[i], max_ending_here + arr[i]); // update max_ending_here

Choose to start new subarray at current element or extend previous subarray

max_so_far = max(max_so_far, max_ending_here); // update max_so_far

Keep track of the best sum found so far

Output

Maximum subarray sum is 6

Complexity Analysis

Time: O(n) because we scan the array once updating sums

Space: O(1) because we use only a few variables, no extra arrays

vs Alternative: Naive approach checks all subarrays with O(n^2) or O(n^3) time, Kadane's is much faster

Edge Cases

All negative numbers

Returns the largest (least negative) single element

DSA C

int max_ending_here = arr[0];

Single element array

Returns that element as max sum

DSA C

int max_ending_here = arr[0];

Array with all positive numbers

Returns sum of entire array

DSA C

max_ending_here = max(arr[i], max_ending_here + arr[i]);

When to Use This Pattern

When asked to find the maximum sum of a continuous subarray, use Kadane's algorithm because it efficiently tracks the best sums in one pass.

Common Mistakes

Mistake: Resetting max_ending_here to zero instead of current element when sum drops below zero
Fix: Reset max_ending_here to current element to handle negative numbers correctly

Mistake: Not updating max_so_far after updating max_ending_here
Fix: Always update max_so_far to keep track of the best sum found

Summary

Finds the maximum sum of any continuous subarray in a list.

Use when you need the largest sum of consecutive elements efficiently.

Keep track of the best sum ending at each position and update the overall best.