Kadane's algorithm

Problem

Given a list of numbers that can be negative, find the contiguous stretch with the largest sum. There are about n²/2 stretches, and summing each costs O(n), so brute force is O(n³); prefix sums bring it to O(n²). Kadane's algorithm gets O(n) time and O(1) space by noticing that you only need the best sum ending at the current index.

Intuition

Walk along the array carrying the best total of any stretch that finishes at your current position. At the next number x you face a choice: attach x to that stretch, or begin a new stretch with x alone. Attaching is better exactly when the stretch you carry has a positive sum, because then it adds something. If the carried sum is zero or negative, it only holds you back, so throw it away.

The overall answer is the largest value that this carried number ever takes. It does not need to look at old positions again, because the carried number already contains the best of them. Every subarray ends somewhere, and at that end the algorithm has computed the best stretch ending there, so none can be missed.

Each bottom cell uses only the one before it. The diagram scrolls sideways on a narrow screen.

Mechanics

The recurrence and its proof

Let f(i) be the largest sum of a non-empty subarray ending at index i. Such a subarray is either just nums[i] or nums[i] attached to a subarray ending at i − 1. In the second case the best choice is the best one ending at i − 1, so

f(i) = nums[i] + max(0, f(i − 1)), and the answer is max over i of f(i).

The proof is by induction on i using exactly that case split, and the max over i covers every possible right end. The "max with 0" is the restart: it drops a carried sum that is not helping.

Recovering the stretch itself

To report where the best stretch is, remember where the current stretch began, resetting it whenever you restart. When a new overall best appears, copy the current start and the current index. Use a strict comparison to keep the leftmost best on ties.

Circular arrays

If the stretch may wrap from the end back to the start, there are two shapes. Either it does not wrap (plain Kadane) or it does, in which case the elements it leaves out form one contiguous stretch in the middle. To make the wrapping stretch as large as possible, leave out the smallest middle stretch: the answer is total − (minimum subarray sum). The minimum subarray comes from running Kadane on the negated values. One trap: if every number is negative, the minimum subarray is the whole array and the wrapping stretch would be empty, which is not allowed, so the answer is the plain Kadane result.

Read the blue cells as one loop: the tail of the row continues into the head. The excluded stretch sits strictly inside.

Maximum product: keep two numbers

For products, multiplying by a negative flips order: the most negative product ending at the previous index becomes the largest after multiplying by a negative. So carry both high and low, the largest and smallest products of a stretch ending here, and for each x take the max and min of x, high * x and low * x. A zero resets both, which is the same restart idea. The answer is the largest high seen.

One buy and one sell

The profit of buying on day i and selling on day j is the sum of the daily changes from i + 1 to j. So the best single trade is the maximum subarray of the changes (or zero, if no trade is better). The min-so-far version is the same recurrence in disguise.

Worked example

Plain. On 3, -4, 2, -1, 5, -6, 1, 4 the best sum ending at each index is 3, -1, 2, 1, 6, 0, 1, 5. The largest is 6, for the stretch from index 2 to index 4.

Circular. The total is 4. The smallest stretch has sum -6 (indices 5 to 5), so the wrapping best is 4 − (-6) = 10, which beats the plain 6. The circular answer is 10. For the all-negative row -3, -2, -5 the wrap would leave out everything, so the answer is the plain maximum -2.

Product. On 2, 3, -2, 4, -1, 5, 0, 2 the (largest, smallest) products ending at each index are 2, 2; 6, 3; -2, -12; 4, -48; 48, -4; 240, -20; 0, 0; 2, 0. The best product is 240.

Implementation

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


def max_subarray_with_span(nums):
    best, ending, begin, span = nums[0], nums[0], 0, (0, 0)
    for i in range(1, len(nums)):
        if ending > 0:
            ending += nums[i]
        else:
            ending, begin = nums[i], i
        if ending > best:
            best, span = ending, (begin, i)
    return best, span

Variations and edge cases

def max_circular(nums):
    total = sum(nums)
    plain = max_subarray(nums)
    lowest = -max_subarray([-x for x in nums])
    if lowest == total:          # every element is in the smallest stretch
        return plain
    return max(plain, total - lowest)


def max_product(nums):
    high = low = best = nums[0]
    for x in nums[1:]:
        high, low = max(x, high * x, low * x), min(x, high * x, low * x)
        best = max(best, high)
    return best

• All negative. Starting best at 0 is a classic bug: it reports an empty stretch. Start from the first element.
• Empty input. The versions above need at least one element; return 0 or raise first if empty input is possible.
• Ties and spans. A strict > keeps the leftmost best stretch, >= the rightmost.
• Zeros in products. A zero makes both high and low zero, and the next number starts fresh through the x option.
• Tuple assignment. In the product version, compute both new values from the old ones; updating high first corrupts the second line.
• Overflow. Python integers do not overflow; in other languages the product version needs care.

Complexity and tradeoffs

• Time: O(n), one pass.
• Space: O(1); only the carried sum, the best, and optionally the span indices.
• Baseline. Brute force is O(n³), or O(n²) with prefix sums.
• Alternatives. A divide-and-conquer solution (best in left half, right half, or crossing the middle) is O(n log n) and is the right tool when you need to merge answers, as in a segment tree.
• When it fails. Kadane maximises a sum; it does not find a stretch with an exact sum or a length constraint such as "at least k elements". For those, prefix sums with a hash map or a deque are needed.

Problems

Maximum Subarray is the core exercise; write it with the span as well. Then the circular version tests whether you understand why the complement argument holds, and the product and tree-path variants show the same carried-value idea in new settings.

Easy

• 121. Best Time to Buy and Sell Stock Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Track the lowest price seen so far, and each day's best profit is today's price minus that minimum.

Medium

• 53. Maximum Subarray Blind 75 Grind 169 NeetCode 150 NeetCode 250
  The best subarray ending here either extends the best one ending at the previous index or starts fresh, whichever is larger.
• 918. Maximum Sum Circular Subarray NeetCode 250
  The best wrapping subarray is the total minus the minimum subarray, unless every number is negative.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 152. Maximum Product Subarray Medium
• 124. Binary Tree Maximum Path Sum Hard

Connections

Kadane's recurrence is a one-dimensional DP that keeps only the previous cell, as in linear DP, and the subarray-sum view comes straight from prefix sums: the best stretch ending at i is the prefix sum at i minus the smallest earlier prefix sum.

Check yourself

References

• Bentley, J., "Programming Pearls: Algorithm Design Techniques", Communications of the ACM 27(9), 1984, which presents the maximum-subarray problem and its linear scan, credited to Jay Kadane.
• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, section 4.1 of the 3rd edition on the maximum-subarray problem.
• Skiena, S., The Algorithm Design Manual, chapter 10 on dynamic programming.
• Sedgewick and Wayne, Algorithms, chapter 1 on analysis of algorithms.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.