practice · medium · from Arrays

Maximum Subarray (Kadane's)

time: O(n)
space: O(1)
tags: arrays · dynamic-programming

in the wild Best continuous window of SLAM confidence — the longest stretch of trusted tracking.

Problem

Given an array of integers nums (which may contain negatives), find the contiguous non-empty subarray with the largest sum and return that sum.

Examples

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] → 6 (subarray [4, -1, 2, 1])
nums = [1] → 1
nums = [-3, -1, -2] → -1 (every subarray has a negative sum; pick the least negative single element)
nums = [5, 4, -1, 7, 8] → 23

Why this is the introduction to dynamic programming

Brute force enumerates every (i, j) pair of indices and sums the slice — O(n²) pairs × O(n) per sum = O(n³). A prefix-sum table cuts the per-pair cost to O(1), but you still pay O(n²) pairs.

The trick — Kadane's algorithm — is a one-pass O(n) solution. The insight is that the best subarray ending exactly at position i either:

extends the best subarray ending at i-1 by including nums[i], or
starts fresh at i (because the previous best was negative, so dragging it forward only hurts).

That's it. One scan, two running variables. This is the simplest example of the "DP on arrays" pattern that powers longest-increasing-subsequence, edit distance, and a hundred interview questions.

Hints

Hint 1 — observe the structure

What's the best subarray ending exactly at index i? Could it relate to the best ending at i - 1?

Hint 2 — the recurrence

Let best_ending_at(i) be the maximum sum of any non-empty subarray that ends at index i. Then:

best_ending_at(i) = max(nums[i],                       # start fresh here
                       best_ending_at(i - 1) + nums[i])  # extend the prior run

The answer is max(best_ending_at(0), best_ending_at(1), …, best_ending_at(n-1)). Now collapse that into two running scalars.

Solution

def max_subarray(nums: list[int]) -> int:
    # Pre: nums is non-empty.
    best_ending_here = nums[0]
    best_overall     = nums[0]
    for n in nums[1:]:
        # Either extend the previous run, or start fresh at n.
        best_ending_here = max(best_ending_here, 0) + n
        best_overall     = max(best_overall, best_ending_here)
    return best_overall

cases = [
    ([-2, 1, -3, 4, -1, 2, 1, -5, 4],  6),
    ([1],                              1),
    ([-7],                            -7),
    ([-3, -1, -2],                    -1),   # all negative → least bad
    ([5, 4, -1, 7, 8],                23),
]
for nums, expected in cases:
    got  = max_subarray(nums)
    mark = "✓" if got == expected else "✗"
    print(f"{mark} max_subarray({nums}) = {got}  (expected {expected})")

function maxSubarray(nums) {
  // Pre: nums.length >= 1.
  let bestEndingHere = nums[0];
  let bestOverall    = nums[0];
  for (let i = 1; i < nums.length; i++) {
    bestEndingHere = Math.max(bestEndingHere, 0) + nums[i];
    bestOverall    = Math.max(bestOverall, bestEndingHere);
  }
  return bestOverall;
}

const cases = [
  [[-2, 1, -3, 4, -1, 2, 1, -5, 4],  6],
  [[1],                              1],
  [[-7],                            -7],
  [[-3, -1, -2],                    -1],
  [[5, 4, -1, 7, 8],                23],
];
for (const [nums, expected] of cases) {
  const got = maxSubarray(nums);
  console.log(`${got === expected ? "✓" : "✗"} maxSubarray(${JSON.stringify(nums)}) = ${got}  (expected ${expected})`);
}

pub fn max_subarray(nums: &[i32]) -> i32 {
    // Pre: nums is non-empty.
    let mut best_ending_here = nums[0];
    let mut best_overall     = nums[0];
    for &n in &nums[1..] {
        // Either extend the previous run, or start a new one at n.
        best_ending_here = best_ending_here.max(0) + n;
        best_overall     = best_overall.max(best_ending_here);
    }
    best_overall
}

fn main() {
    let cases: &[(&[i32], i32)] = &[
        (&[-2, 1, -3, 4, -1, 2, 1, -5, 4],  6),
        (&[1],                              1),
        (&[-7],                            -7),
        (&[-3, -1, -2],                    -1),
        (&[5, 4, -1, 7, 8],                23),
    ];
    for (nums, expected) in cases {
        let got  = max_subarray(nums);
        let mark = if got == *expected { "✓" } else { "✗" };
        println!("{mark} max_subarray({:?}) = {}  (expected {})", nums, got, expected);
    }
}

#include <algorithm>
#include <iostream>
#include <vector>

int max_subarray(const std::vector<int>& nums) {
    // Pre: nums.size() >= 1.
    int best_ending_here = nums[0];
    int best_overall     = nums[0];
    for (size_t i = 1; i < nums.size(); ++i) {
        best_ending_here = std::max(best_ending_here, 0) + nums[i];
        best_overall     = std::max(best_overall, best_ending_here);
    }
    return best_overall;
}

int main() {
    struct Case { std::vector<int> nums; int expected; };
    std::vector<Case> cases = {
        {{-2, 1, -3, 4, -1, 2, 1, -5, 4},  6},
        {{1},                              1},
        {{-7},                            -7},
        {{-3, -1, -2},                    -1},
        {{5, 4, -1, 7, 8},                23},
    };
    for (auto& c : cases) {
        int got = max_subarray(c.nums);
        std::cout << (got == c.expected ? "✓" : "✗") << " max_subarray({";
        for (size_t i = 0; i < c.nums.size(); ++i)
            std::cout << c.nums[i] << (i + 1 < c.nums.size() ? "," : "");
        std::cout << "}) = " << got << "  (expected " << c.expected << ")\n";
    }
}

#include <stdio.h>

int max_subarray(const int* nums, int n) {
    // Pre: n >= 1.
    int best_ending_here = nums[0];
    int best_overall     = nums[0];
    for (int i = 1; i < n; i++) {
        int prev = best_ending_here > 0 ? best_ending_here : 0;
        best_ending_here = prev + nums[i];
        if (best_ending_here > best_overall) best_overall = best_ending_here;
    }
    return best_overall;
}

static void show(const int* nums, int n, int expected) {
    int got = max_subarray(nums, n);
    printf("%s max_subarray({", got == expected ? "✓" : "✗");
    for (int i = 0; i < n; i++) printf("%d%s", nums[i], i + 1 < n ? "," : "");
    printf("}) = %d  (expected %d)\n", got, expected);
}

int main(void) {
    int a[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};  show(a, 9,  6);
    int b[] = {1};                              show(b, 1,  1);
    int c[] = {-7};                             show(c, 1, -7);
    int d[] = {-3, -1, -2};                     show(d, 3, -1);
    int e[] = {5, 4, -1, 7, 8};                 show(e, 5, 23);
    return 0;
}

idle

The key trick is the same in every language: best_ending_here = max(best_ending_here, 0) + n. If the running sum has gone negative, the next subarray is better off starting fresh at n than dragging the negative tail forward. Two running scalars, one pass, every language.

Complexity

Time: O(n) — single pass; constant work per element.
Space: O(1) — two scalars, no auxiliary array.
vs brute force: The naïve O(n³) double-loop-plus-sum, or O(n²) with a prefix-sum table. Kadane's collapses both axes into one pass.

In the wild

The "running-state with reset" pattern shows up everywhere:

Stock trading. max profit = max over i,j of (price[j] - price[i]) is Kadane's on the array of daily diffs.
Signal processing. "Find the longest stretch where the signal stays above threshold" — Kadane's on a thresholded array.
Robot tracking. "Find the longest continuous window where SLAM confidence stayed high" — same shape, with confidence diffs.

Variations

Return the subarray, not just the sum. Track the start/end indices alongside the running scalars.
2D version (maximum submatrix sum). Fix the top and bottom row, collapse each column to a single integer, run Kadane's on that. O(n² · m) for an n × m matrix.
Subarray with at most k negative numbers. Sliding-window variant — different algorithm family.