Kadane's Algorithm

EditorialUpdated Oct 25, 2026

Every subarray, or one pass?

A share price changed by [-2, 1, -3, 4, -1, 2, 1, -5, 4] over nine days. Which run of consecutive days gained the most? That's Maximum Subarray: the largest sum of a contiguous subarray. Here it's days 3 to 6, 4 − 1 + 2 + 1 = 6.

The direct way tries every start and every end:

def max_sub_array_slow(nums):
    best = nums[0]
    for start in range(len(nums)):
        total = 0
        for end in range(start, len(nums)):      # every subarray that starts here
            total += nums[end]
            best = max(best, total)
    return best

It returns 6, after trying all n(n + 1)/2 subarrays: for 100,000 days that's 5,000,050,000. Yet look at the answer from where it ends. The best subarray that ends on day i either is day i on its own, or is day i added to the best subarray that ends on day i − 1. So one number carried from day to day is enough, and the only question each day is: keep going, or start over here?

The values -2, 1, -3, 4, -1, 2, 1, -5, 4 in a row, and below them their running totals as a walk of dots: 0, −2, −1, −4, 0, −1, 1, 2, −3, 1. A dashed line follows the lowest total so far; it steps down at fence 1 (−2) and fence 3 (−4), each marked a new low: start over. From −4 at fence 3 the walk climbs to 2 at fence 7, a climb of 6. The values in between, 4, −1, 2, 1, are the best subarray.

Keep going, or start over

Call cur the best sum of a subarray that ends at the value before this one. Adding the next value x gives cur + x; starting over gives just x. When cur is negative, cur + x is smaller than x, so starting over wins; when it isn't, extending wins.

Why that's always safe: if a subarray begins with a stretch whose sum is negative, cutting that stretch off leaves a bigger sum. So the best subarray never starts with a negative running sum, and dropping one the moment it appears can't lose the answer.

Make the decision yourself below. At each value, extend the current subarray or start a new one. The widget keeps your running sum and your best, tells you what the rule above would have done, and at the end checks your best against the true maximum.

Extend or Restart: decide at every value, and see what Kadane's rule would do

The rule fits in one line: cur = max(x, cur + x). Starting over exactly when cur is negative is the same thing (when cur is 0 both choices give the same sum).

The template

Carry cur, the best sum ending here, and best, the largest cur seen:

Kadane's on [-2, 1, -3, 4, -1, 2, 1, -5, 4] — The shaded cells are the subarray that cur stands for; it restarts when cur goes negative.

int maxSubArray(const vector<int>& nums) {
    int cur = nums[0], best = nums[0];          // the best sum ending here, and the best anywhere
    for (size_t i = 1; i < nums.size(); i++) {
        cur = max(nums[i], cur + nums[i]);      // start over at nums[i], or extend: whichever is bigger
        best = max(best, cur);
    }
    return best;
}

def max_sub_array(nums):
    cur = best = nums[0]                        # the best sum ending here, and the best anywhere
    for x in nums[1:]:
        cur = max(x, cur + x)                   # start over at x, or extend: whichever is bigger
        best = max(best, cur)
    return best

static int maxSubArray(int[] nums) {
    int cur = nums[0], best = nums[0];          // the best sum ending here, and the best anywhere
    for (int i = 1; i < nums.length; i++) {
        cur = Math.max(nums[i], cur + nums[i]); // start over at nums[i], or extend: whichever is bigger
        best = Math.max(best, cur);
    }
    return best;
}

function maxSubArray(nums) {
    let cur = nums[0], best = nums[0];          // the best sum ending here, and the best anywhere
    for (let i = 1; i < nums.length; i++) {
        cur = Math.max(nums[i], cur + nums[i]); // start over at nums[i], or extend: whichever is bigger
        best = Math.max(best, cur);
    }
    return best;
}

Each prints 6, 1, 23 and -1 for [-2, 1, -3, 4, -1, 2, 1, -5, 4], [1], [5, 4, -1, 7, 8] and [-3, -1, -2]. One pass and two numbers: O(n) time, O(1) space. Start both at the first value, not at 0: the subarray can't be empty, so on [-3, -1, -2] the answer is -1, not 0.

The same answer from running totals

Introduction to Prefix Sums turned every subarray into two fences on the walk of running totals, its sum the rise from one to the other. The best subarray ending at a fence is that fence's total minus the lowest total before it. So keep the lowest total so far, and the answer is the biggest climb above it:

def max_sub_array_by_totals(nums):
    total, lowest = 0, 0                        # the running total, and the lowest total before this point
    best = nums[0]
    for x in nums:
        total += x
        best = max(best, total - lowest)        # the climb from the lowest earlier total
        lowest = min(lowest, total)             # only now may this total serve as a start
    return best

It prints 6, 1, 23 and -1 for the same arrays. In the figure above, the lowest total drops at fences 1 and 3, and those are exactly where Kadane's starts over: cur goes negative at the same moment the walk sets a new low. It's also Best Time to Buy and Sell Stock in disguise: buy at the lowest price so far, sell at the biggest climb.

Which subarray, not just its sum

Maximum Sum Subarray with Indices wants where the best subarray is. Remember where the current subarray started, and copy the span whenever cur sets a new best:

def max_sub_array_with_indexes(nums):
    cur, start = nums[0], 0
    best, best_l, best_r = nums[0], 0, 0
    for i in range(1, len(nums)):
        if cur < 0:                             # a negative running sum only drags what follows down
            cur, start = nums[i], i
        else:
            cur += nums[i]
        if cur > best:                          # record the span when the best is set, not at the end
            best, best_l, best_r = cur, start, i
    return best, best_l, best_r

It prints (6, 3, 6) for [-2, 1, -3, 4, -1, 2, 1, -5, 4]: the sum 6, from index 3 to index 6. Using cur > best keeps the first of several equally good subarrays; >= would keep the last.

When the array wraps around

Maximum Sum Circular Subarray: the end of the array joins its start, so a subarray may wrap around. A wrapping subarray is the whole array minus a non-wrapping piece in the middle, and it's biggest when that piece is the smallest-sum subarray. So run Kadane's twice, once for the largest sum and once for the smallest, and take the larger of best and total − worst.

One trap: when every value is negative, the smallest subarray is the whole array, and total − worst is 0, the sum of taking nothing. That isn't allowed, so return best then:

def max_subarray_sum_circular(nums):
    best = worst = cur_best = cur_worst = total = nums[0]
    for x in nums[1:]:
        cur_best = max(x, cur_best + x)
        best = max(best, cur_best)
        cur_worst = min(x, cur_worst + x)       # the same scan for the smallest sum
        worst = min(worst, cur_worst)
        total += x
    if best < 0:                                # every value is negative: wrapping would mean taking nothing
        return best
    return max(best, total - worst)             # a wrapping subarray is everything except the worst one

It prints 3, 10 and −2 for [1, -2, 3, -2], [5, -3, 5] and [-3, -2, -3]. In [5, -3, 5] the best subarray wraps: 5 and 5, joined around the end, with the −3 left out.

Spotting it

Reach for Kadane's when you see:

the largest (or smallest) sum of a contiguous subarray, with no other limit;
a best stretch of days, gains, scores or profits, where bad stretches can be skipped;
the same on a circle (Kadane's for the best and the worst).

And the near-misses:

a sum that must equal k, or be a multiple of k: that's running totals and a hash map, in Prefix Sums with a Hash Map.
a length limit ("at most k values"): a sliding window, or a monotonic deque over running totals.
a subsequence rather than a subarray: skipping values is allowed, so just add the positive ones (or use dynamic programming when there are more rules).
a product instead of a sum: one number isn't enough, because a negative value turns the smallest product into the largest. That's Kadane's Algorithm with More State.
a grid: fix a top and bottom row, add up each column between them, and run Kadane's on those sums.

Common mistakes

Starting best at 0. cur = best = 0

On [-3, -1, -2] it returns 0: the empty subarray sneaks in. The answer is −1, the largest single value. Start both at nums[0].

Updating best before cur. best = max(best, cur) above cur = max(x, cur + x)

Then the subarray ending at the last value is never compared. On [2, -1, 3] it returns 2, where 2 − 1 + 3 = 4.

Forgetting the all-negative case on a circle. No if best < 0 check

On [-3, -2, -3], total − worst is −8 − (−8) = 0, and the code returns 0. The answer is −2: the subarray can't be empty, wrapped or not.

Check yourself

Quiz

1 / 6

Multiple choice

cur is the best sum of a subarray ending just before the value x. When should the subarray ending at x start over at x?

Practice problems

From easier to harder:

Maximum Subarray: the template.
Maximum Sum Subarray with Indices: the template, keeping the span.
Maximum Sum Circular Subarray: Kadane's for the best and the worst.

Next, Kadane's Algorithm with More State handles the cases where one running number isn't enough: products, one deletion, and alternating signs.