Kadane’s Algorithm

The problem

You run a small shop and you've logged each day's profit and loss for the year: [-2, 1, -3, 4, -1, 2, 1, -5, 4]. Some days you made money, some you lost it. Your accountant asks a sharp question: "What was your best continuous streak — the run of consecutive days with the highest total profit?"

You want the single contiguous stretch whose numbers add up to the most. Not the biggest day, not the sum of all good days — one unbroken window. With a year it's easy to eyeball. With a decade of daily data, or a sensor logging every second, you need an algorithm.

A first attempt

Try every possible stretch. Pick a start day, pick an end day, add up everything between, keep the biggest total you see:

def max_subarray_brute(nums):
    best = nums[0]
    for i in range(len(nums)):
        total = 0
        for j in range(i, len(nums)):
            total += nums[j]      # extend the window ending at j
            best = max(best, total)
    return best

There are about n²/2 stretches (see Array Traversal Tricks), and this visits each — O(n²). Fine for a year. For a million data points, that's 500 billion additions. Too slow.

The insight

Walk left to right and ask a single, local question at each day: "Is the best streak ending right here better if I extend yesterday's streak, or if I start fresh today?"

If yesterday's running total was positive, it can only help — carry it forward and add today. If it was negative, it's dead weight — drop it and start a new streak at today. Track that running total, and remember the largest value it ever reaches. That's Kadane's algorithm: one pass, O(n).

current = max(today, current + today)   # extend, or start fresh
best    = max(best, current)            # remember the champion

How it works

Run it on [-2, 1, -3, 4, -1, 2, 1, -5, 4].

day:        -2   1  -3   4  -1   2   1  -5   4
current:    -2   1  -2   4   3   5   6   1   5
best:       -2   1   1   4   4   5   6   6   6   -> answer 6

Notice day 2: current was 1, adding -3 gives -2, but starting fresh at -3 is worse, so current = -2. Then day 3 sees that -2 is negative dead weight and restarts at 4. That restart is the whole idea.

The code

def max_subarray(nums):
    best = current = nums[0]
    for x in nums[1:]:
        current = max(x, current + x)   # extend or start fresh
        best = max(best, current)
    return best

function maxSubarray(nums: number[]): number {
  let best = nums[0];
  let current = nums[0];
  for (let i = 1; i < nums.length; i++) {
    current = Math.max(nums[i], current + nums[i]);
    best = Math.max(best, current);
  }
  return best;
}

int maxSubarray(int[] nums) {
    int best = nums[0], current = nums[0];
    for (int i = 1; i < nums.length; i++) {
        current = Math.max(nums[i], current + nums[i]);
        best = Math.max(best, current);
    }
    return best;
}

int max_subarray(int *nums, int n) {
    int best = nums[0], current = nums[0];
    for (int i = 1; i < n; i++) {
        int extend = current + nums[i];
        current = nums[i] > extend ? nums[i] : extend;
        best = best > current ? best : current;
    }
    return best;
}

#include <vector>
#include <algorithm>
using namespace std;

int maxSubarray(vector<int>& nums) {
    int best = nums[0], current = nums[0];
    for (size_t i = 1; i < nums.size(); i++) {
        current = max((int)nums[i], current + nums[i]);
        best = max(best, current);
    }
    return best;
}

Complexity

From quadratic to linear by asking one local question per element instead of re-summing every window.

When to use it

Practice

Recap

• Kadane's algorithm finds the maximum-sum contiguous subarray in O(n) time and O(1) space, replacing the O(n²) check-every-stretch approach.
• The core move is local: at each element, extend the running total if it helps or restart from the current element if the running total has gone negative.
• Seed best and current with nums[0] so arrays of all-negative numbers return a real element instead of a phantom zero.