Kadane's Algorithm: Maximum Subarray Sum in O(n)

By Engr. Henry Akpan

The Best Stretch of Days

A shop records its daily profit (or loss) for two weeks. Over which run of consecutive days did it make the most money? A trader wants the best period to have held a share. A signal-processing program wants the strongest burst in a noisy reading. All of these are the maximum subarray problem: find the contiguous part of a list of numbers with the largest sum. Checking every possible stretch takes O(n²) or O(n³) time, but Kadane's algorithm solves it in a single pass, in O(n) time and O(1) extra memory. This tutorial explains the brute-force approach, the key insight behind Kadane's algorithm, a step-by-step trace, how to recover the start and end positions, the all-negative case, and common variations, with Python code whose outputs have been checked by running it.

The Maximum Subarray Problem

Given a list such as [-2, 1, -3, 4, -1, 2, 1, -5, 4], find the contiguous sublist with the largest sum. Here the answer is [4, -1, 2, 1], with sum 6. Note that "contiguous" matters: we cannot skip the −1 to take just 4, 2 and 1, because they are not next to each other.

If every number were positive, the answer would be the whole list. If every number were negative, it would be the single largest (least negative) number. The problem is interesting because of the mixture.

Brute Force: Try Every Subarray

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]          # sum of nums[i..j], extended one step at a time
            best = max(best, total)
    return best

data = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_brute(data))

Output:

6

This checks every start i and every end j, which is about n²/2 subarrays: O(n²) time. For 100,000 numbers that is 5 billion steps, far too slow.

The Key Insight Behind Kadane's Algorithm

Scan the list from left to right and ask, at each position: what is the best sum of a subarray that ends exactly here?

A subarray ending at position i either

  • extends the best subarray ending at position i − 1 by adding nums[i], or
  • starts fresh at position i, with just nums[i].

We should start fresh whenever the best sum ending at the previous position is negative, because carrying a negative total forward can only make things worse. So:

best_ending_here = max(nums[i], best_ending_here + nums[i])

The overall answer is the largest best_ending_here seen anywhere. This is a tiny example of dynamic programming: each step reuses the answer to the previous step instead of recomputing it.

Kadane's Algorithm in Python

def kadane(nums):
    current = best = nums[0]
    for x in nums[1:]:
        current = max(x, current + x)
        best = max(best, current)
    return best

print(kadane(data))
print(kadane([5, 4, -1, 7, 8]))
print(kadane([-8, -3, -6, -2, -5, -4]))

Output:

6
23
-2

One loop, two variables: O(n) time and O(1) extra space. Starting with nums[0] (rather than 0) makes the all-negative case work correctly, returning the largest single element, −2.

Tracing Kadane's Algorithm Step by Step

Printing the two variables at each step shows the "extend or restart" decision:

def kadane_trace(nums):
    current = best = nums[0]
    print(f"x={nums[0]:3}  current={current:3}  best={best:3}")
    for x in nums[1:]:
        action = "extend" if current + x > x else "restart"
        current = max(x, current + x)
        best = max(best, current)
        print(f"x={x:3}  current={current:3}  best={best:3}  ({action})")

kadane_trace(data)

Output:

x= -2  current= -2  best= -2
x=  1  current=  1  best=  1  (restart)
x= -3  current= -2  best=  1  (extend)
x=  4  current=  4  best=  4  (restart)
x= -1  current=  3  best=  4  (extend)
x=  2  current=  5  best=  5  (extend)
x=  1  current=  6  best=  6  (extend)
x= -5  current=  1  best=  6  (extend)
x=  4  current=  5  best=  6  (extend)

At x = 4 the running total was −2, so the algorithm restarted. From there it kept extending, reaching 6 at the 7th element. Even after the −5 it kept extending, because the running total (1) was still positive and might help later; but it never beat 6.

Finding Where the Best Subarray Starts and Ends

Usually you need the positions too, such as which days gave the best profit. Track where the current run started, and save the positions whenever best improves:

def kadane_with_indices(nums):
    current, best = nums[0], nums[0]
    start = best_start = best_end = 0
    for i in range(1, len(nums)):
        if current + nums[i] < nums[i]:
            current = nums[i]
            start = i                 # restart here
        else:
            current += nums[i]
        if current > best:
            best, best_start, best_end = current, start, i
    return best, best_start, best_end

profits = [-300, 500, 700, -1000, 400, 600, -200, 900, -1500, 200]
total, s, e = kadane_with_indices(profits)
print(f"Best total N{total} from day {s + 1} to day {e + 1}: {profits[s:e + 1]}")

Output:

Best total N1900 from day 2 to day 8: [500, 700, -1000, 400, 600, -200, 900]

The best run even includes the big loss on day 4. After days 2 and 3 the running total was 1,200, and the loss only brought it down to 200, which is still positive, so it was worth carrying forward into the strong days that followed. Days 5 to 8 alone made 1,700, less than 1,900. Restarting only pays when the running total drops below zero.

Checking Kadane's Algorithm Against Brute Force

A good habit for any clever algorithm is to test it against a simple, obviously correct version on many random inputs:

import random

random.seed(1)
for trial in range(1000):
    nums = [random.randint(-10, 10) for _ in range(random.randint(1, 15))]
    assert kadane(nums) == max_subarray_brute(nums), nums
print("1000 random tests passed")

Output:

1000 random tests passed

Variations

Allowing an empty subarray. If the problem says an empty subarray (sum 0) is allowed, start with current = best = 0 and use current = max(0, current + x). Then an all-negative list gives 0.

Maximum product subarray. For products, a negative number can turn the smallest product into the largest, so track both the maximum and the minimum product ending at each position, swapping them when x is negative.

Circular arrays. If the list wraps around (the last element is next to the first), the best subarray either doesn't wrap (ordinary Kadane) or does wrap. A wrapping subarray is everything except a middle stretch, so its sum is the total minus the minimum subarray sum (found with Kadane using min). Take the larger, unless every number is negative.

def max_circular(nums):
    best_normal = kadane(nums)
    if best_normal < 0:
        return best_normal            # all negative
    cur = worst = nums[0]
    for x in nums[1:]:
        cur = min(x, cur + x)
        worst = min(worst, cur)
    return max(best_normal, sum(nums) - worst)

print(max_circular([5, -3, 5]), max_circular([1, -2, 3, -2]), max_circular([-3, -2, -3]))

Output:

10 3 -2

Two dimensions. The largest-sum rectangle in a grid can be found by fixing a pair of rows, adding up each column between them, and running Kadane on those column sums, in O(rows² × columns) time.

Summary

  • The maximum subarray problem asks for the contiguous stretch with the largest sum.
  • Brute force checks every subarray in O(n²); Kadane's algorithm needs one pass, O(n) time and O(1) space.
  • Key step: current = max(x, current + x), meaning extend the run or restart at x; best is the largest current seen.
  • Track a start index and save positions when best improves to recover the subarray itself.
  • Variations handle empty subarrays, products, circular arrays and 2D grids.

Related Tutorials