Kadane’s Algorithm: Working, Explanation, and Maximum Subarray Problem

The first time I encountered the maximum subarray problem, I tried to solve it by checking every possible subarray, and I remember being frustrated at how slow that felt for large inputs. Kadane’s Algorithm was my introduction to the idea that dynamic programming doesn’t have to be complicated — sometimes it’s just a single running variable and a moment of insight. It finds the contiguous subarray with the largest sum in a one-dimensional array of numbers, and it does so in a single pass. I now think of it as one of the cleanest possible examples of dynamic programming thinking, and it’s usually the first “real” DP algorithm people learn.

History and Background

I credit this algorithm to Jay Kadane, a computer scientist who came up with the linear-time solution in 1984. What I find interesting is the backstory: the maximum subarray problem was originally posed by Ulf Grenander in the context of pattern recognition in digitized images, and it was popularized more broadly by a paper from Jon Bentley, who discussed multiple solutions of increasing sophistication (from cubic, to quadratic, to Kadane’s linear approach) in his “Programming Pearls” column. Bentley credited Kadane for the elegant linear solution after hearing about it, and the name has stuck ever since, even though Kadane himself didn’t publish it as a standalone paper.

Problem Statement

I am given an array of n integers, which may include negative numbers, and I need to find the contiguous subarray (containing at least one number) that has the largest possible sum. A brute-force approach checks all O(n^2) subarrays (or O(n^3) if I recompute each subarray’s sum from scratch), which becomes impractical for large arrays. Kadane’s algorithm solves this in a single linear pass by making a greedy-but-provably-optimal local decision at every position.

Core Concepts

• Subarray: a contiguous slice of the array, as opposed to a subsequence, which can skip elements.
• Local maximum sum ending at index i: the maximum sum of a subarray that ends exactly at position i. This is the quantity Kadane’s algorithm tracks and updates.
• Global maximum sum: the best local maximum seen across the entire array, which is the final answer.
• Reset decision: at each step, the algorithm decides whether extending the previous subarray is better than starting fresh at the current element.

How It Works

I maintain two variables as I scan the array left to right:

1. current_max — the maximum sum of a subarray ending at the current index.
2. global_max — the maximum sum found so far, across all positions.

For each element x in the array, I update:

• current_max = max(x, current_max + x) — I either extend the previous subarray by including x, or I start a brand-new subarray at x, whichever gives a larger sum.
• global_max = max(global_max, current_max) — I update the best answer seen so far.

By the time I finish scanning the array, global_max holds the answer.

Working Principle

The key realization that makes this work is that if current_max (the best subarray ending at the previous index) ever becomes negative, it can never help me — adding a negative number to any future subarray sum only hurts it. So whenever current_max + x < x, meaning the running sum has turned into a net negative contribution, I should discard it and restart from the current element. This greedy discarding is safe precisely because I’m not trying to remember every possible starting point — I only need the best sum ending at each index, and that value only depends on the best sum ending at the previous index, which is the essence of optimal substructure in dynamic programming.

Mathematical Foundation

Formally, I define:

$$ S(i) = \max(A[i],\ S(i-1) + A[i]) $$

where S(i) is the maximum subarray sum ending at index i, and A[i] is the array element at index i, with the base case S(0) = A[0].

The final answer is:

$$ \text{MaxSubarraySum} = \max_{0 \leq i < n} S(i) $$

This recurrence has optimal substructure: the optimal solution ending at i depends only on the optimal solution ending at i-1, and it has overlapping subproblems in the general dynamic programming sense, although in this specific case I don’t even need to store the full S array since each S(i) only depends on S(i-1).

Diagrams

flowchart TD
    A[Start: current_max = A0, global_max = A0] --> B[i = 1]
    B --> C{i < n?}
    C -- No --> H[Return global_max]
    C -- Yes --> D["current_max = max(A[i], current_max + A[i])"]
    D --> E["global_max = max(global_max, current_max)"]
    E --> F[i = i + 1]
    F --> C

graph LR
    subgraph Array values
    A1["-2"] --> A2["1"] --> A3["-3"] --> A4["4"] --> A5["-1"] --> A6["2"] --> A7["1"] --> A8["-5"] --> A9["4"]
    end
    style A4 fill:#9f6
    style A5 fill:#9f6
    style A6 fill:#9f6
    style A7 fill:#9f6

Pseudocode

function maxSubArray(A, n):
    current_max = A[0]
    global_max = A[0]
    for i from 1 to n - 1:
        current_max = max(A[i], current_max + A[i])
        global_max = max(global_max, current_max)
    return global_max

Step-by-Step Example

Consider the array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

I trace current_max and global_max at each index:

The final answer is 6, coming from the subarray [4, -1, 2, 1].

Time Complexity

• Best case: O(n) — the algorithm always makes exactly one pass, regardless of the input’s structure.
• Average case: O(n).
• Worst case: O(n) — there is no input that causes extra work; this is a strictly linear-time algorithm.

Space Complexity

Kadane’s algorithm uses O(1) extra space, since it only needs two scalar variables (current_max and global_max) regardless of the input array’s size. If I also want to recover the actual subarray (not just its sum), I need a few more scalar variables to track the start and end indices, which still keeps the space usage constant.

Correctness Analysis

I prove correctness by induction on the recurrence I defined earlier. The base case is trivially correct: the best subarray ending at index 0 is just A[0]. For the inductive step, assume S(i-1) correctly holds the maximum subarray sum ending at index i-1. Then any subarray ending at index i either consists of just A[i] alone, or it extends some subarray ending at i-1 by one more element. Since S(i-1) is by assumption the best possible sum for a subarray ending at i-1, extending it gives S(i-1) + A[i], and no other choice of subarray ending at i-1 could produce a larger extended sum. Taking the maximum of these two cases therefore correctly computes S(i). Since the global answer is the maximum of all S(i), and each S(i) is proven correct by induction, the algorithm as a whole is correct.

Advantages

• Extremely simple to implement, with just a few lines of code.
• Runs in linear time and constant space, which is optimal for this problem — I cannot do better than examining every element at least once.
• Easily extended to also return the subarray’s start and end indices, not just its sum.
• Serves as a foundational example for teaching dynamic programming with rolling/scalar state instead of full memoization tables.

Disadvantages

• The basic version only returns the maximum sum, not the subarray itself, unless I explicitly track indices.
• It assumes a one-dimensional, contiguous subarray; extending it to 2D (maximum sum submatrix) or non-contiguous subsequence variants requires different techniques.
• If all elements are required to be included (i.e., empty subarrays disallowed) versus allowed, the initialization and edge-case handling differs and is a common source of subtle bugs, particularly with all-negative arrays.

Applications

• Financial analysis, such as finding the best contiguous period of stock price gains (maximum profit over a date range).
• Image processing, where 2D extensions of Kadane’s algorithm find regions of maximum “intensity” or “signal” within a matrix.
• Bioinformatics, for identifying regions of a genome with the highest concentration of certain markers.
• Signal processing, to detect the interval with maximum cumulative signal strength.
• Sports and gaming analytics, such as identifying a team’s best consecutive scoring streak.

Implementation in C

#include <stdio.h>

/* Returns the maximum subarray sum and also records start/end indices */
int maxSubArray(int A[], int n, int *start, int *end) {
    int current_max = A[0];
    int global_max = A[0];
    int temp_start = 0;

    *start = 0;
    *end = 0;

    for (int i = 1; i < n; i++) {
        if (A[i] > current_max + A[i]) {
            /* Starting fresh at A[i] is better than extending */
            current_max = A[i];
            temp_start = i;
        } else {
            /* Extending the previous subarray is better */
            current_max = current_max + A[i];
        }

        if (current_max > global_max) {
            global_max = current_max;
            *start = temp_start;
            *end = i;
        }
    }

    return global_max;
}

int main() {
    int A[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = sizeof(A) / sizeof(A[0]);
    int start, end;

    int result = maxSubArray(A, n, &start, &end);

    printf("Maximum subarray sum is: %d\n", result);
    printf("Subarray is from index %d to %d: [", start, end);
    for (int i = start; i <= end; i++) {
        printf("%d", A[i]);
        if (i != end) printf(", ");
    }
    printf("]\n");

    return 0;
}

#include <stdio.h>

/* Returns the maximum subarray sum and also records start/end indices */
int maxSubArray(int A[], int n, int *start, int *end) {
    int current_max = A[0];
    int global_max = A[0];
    int temp_start = 0;

    *start = 0;
    *end = 0;

    for (int i = 1; i < n; i++) {
        if (A[i] > current_max + A[i]) {
            /* Starting fresh at A[i] is better than extending */
            current_max = A[i];
            temp_start = i;
        } else {
            /* Extending the previous subarray is better */
            current_max = current_max + A[i];
        }

        if (current_max > global_max) {
            global_max = current_max;
            *start = temp_start;
            *end = i;
        }
    }

    return global_max;
}

int main() {
    int A[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = sizeof(A) / sizeof(A[0]);
    int start, end;

    int result = maxSubArray(A, n, &start, &end);

    printf("Maximum subarray sum is: %d\n", result);
    printf("Subarray is from index %d to %d: [", start, end);
    for (int i = start; i <= end; i++) {
        printf("%d", A[i]);
        if (i != end) printf(", ");
    }
    printf("]\n");

    return 0;
}

Sample Input and Output

Input:

A = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Output:

Maximum subarray sum is: 6
Subarray is from index 3 to 6: [4, -1, 2, 1]

Optimization Techniques

• In-place index tracking: as shown in the C implementation above, I track start and end indices alongside the sums without any extra passes, avoiding a second traversal to recover the subarray.
• Divide and conquer alternative: while Kadane’s is already optimal at O(n), understanding the O(n log n) divide-and-conquer solution is useful groundwork for the 2D maximum submatrix problem, where Kadane’s 1D algorithm is applied as a subroutine.
• All-negative array handling: I make sure my initialization (current_max = global_max = A[0]) correctly handles arrays where every element is negative, since naively initializing sums to 0 would incorrectly allow an “empty” subarray with sum 0.
• Streaming adaptation: because Kadane’s only needs the previous state, it adapts naturally to streaming data where I see one number at a time and want to maintain a running best subarray sum without storing the whole array.

Common Mistakes

• Initializing current_max or global_max to 0 instead of A[0], which silently produces wrong answers when all elements are negative.
• Forgetting to reset current_max properly, i.e., using current_max = max(0, current_max + A[i]), which implicitly assumes the empty subarray is allowed — this is only correct if the problem permits an empty subarray with sum zero.
• Confusing the maximum sum subarray problem with the maximum sum subsequence problem, which allows skipping elements and needs a different algorithm.
• Not handling single-element or empty arrays as edge cases before starting the main loop.

Further Reading

• Bentley, J. “Programming Pearls,” Column on Algorithm Design Techniques, Addison-Wesley: https://www.pearson.com/en-us/subject-catalog/p/programming-pearls/P200000003480
• GeeksforGeeks, “Kadane’s Algorithm”: https://www.geeksforgeeks.org/dsa/largest-sum-contiguous-subarray/
• Wikipedia, “Maximum subarray problem”: https://en.wikipedia.org/wiki/Maximum_subarray_problem
• MIT OpenCourseWare, Introduction to Algorithms, Dynamic Programming lectures: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/