Kadane's / Maximum Subarray

Given an array of integers, some positive, some negative, find the contiguous subarray with the largest sum. This is the maximum subarray problem, and it has one of the most elegant solutions in all of computer science: Kadane's algorithm, which solves it in a single pass.

The brute force approach is to try every possible subarray. There are $O(n²)$ of them, and computing each sum takes up to $O(n)$ time, giving $O(n³)$. You can optimize to $O(n²)$ with prefix sums. But Kadane's does it in $O(n)$ with $O(1)$ space: one loop, two variables, and a single elegant idea.

The idea

Imagine you are walking through the array from left to right, accumulating a running sum. At each position, you face a simple question: should I extend the subarray I have been building, or should I throw it away and start fresh from here?

The answer is obvious once you frame it this way. If your running sum is positive, it can only help: adding it to the current element makes things at least as good as starting over. But if the running sum has gone negative, it is dead weight. A negative prefix will drag down anything that comes after it, so you are strictly better off starting a new subarray from the current element.

That decision is captured in one line: cur = max(num, cur + num). Either start fresh (num) or extend (cur + num). After making this choice, you check if the new running sum beats your global best. That is the entire algorithm.

Walking through an example

Consider the array [-2, 1, -3, 4, -1, 2, 1, -5, 4].

Start at -2. Running sum is -2, best is -2. Move to 1. Should we extend (-2 + 1 = -1) or start fresh (1)? Starting fresh is better. Running sum becomes 1, best becomes 1. Move to -3. Extend: 1 + (-3) = -2. Start fresh: -3. Extending is better (less negative). Running sum is -2, best stays 1. Move to 4. Extend: -2 + 4 = 2. Start fresh: 4. Starting fresh wins. Running sum is 4, best becomes 4. Move to -1. Extend: 4 + (-1) = 3. Better than starting fresh at -1. Running sum is 3, best stays 4. Move to 2. Extend: 3 + 2 = 5. Running sum is 5, best becomes 5. Move to 1. Extend: 5 + 1 = 6. Running sum is 6, best becomes 6. Move to -5. Extend: 6 + (-5) = 1. Better than -5. Running sum is 1, best stays 6. Move to 4. Extend: 1 + 4 = 5. Running sum is 5, best stays 6.

The answer is 6, corresponding to the subarray [4, -1, 2, 1]. Notice how the algorithm never looked backward. It never reconsidered a decision. Every subarray ending at each position was implicitly evaluated, and the max operation pruned away every suboptimal one.

The code

def maxSubArray(nums):
    cur = best = nums[0]
    for num in nums[1:]:
        cur = max(num, cur + num)
        best = max(best, cur)
    return best

That is the whole thing. Two variables: cur tracks the best subarray ending at the current position, and best tracks the best subarray seen anywhere so far. The first max decides whether to extend or restart. The second max updates the global answer.

Why it works: the DP perspective

Kadane's algorithm is dynamic programming, even though it does not look like it. Define dp[i] as the maximum subarray sum ending at index i. The recurrence is dp[i] = max(nums[i], dp[i-1] + nums[i]): either the best subarray ending here is just the element itself (start fresh) or it extends the best subarray ending at the previous position. The answer to the original problem is max(dp[0], dp[1], ..., dp[n-1]).

Since dp[i] only depends on dp[i-1], we do not need the array. A single variable cur suffices. The variable best tracks the running maximum across all dp[i] values. This is the same rolling-variable optimization from linear 1D DP, taken to its extreme: the "DP table" is a single number.

The initialization trap

The most common bug in Kadane's algorithm is initializing cur and best to 0 instead of nums[0]. This works fine when the array has at least one positive number, because the maximum subarray sum will be positive. But if all elements are negative, say [-3, -5, -1, -2], then a zero initialization returns 0, implying the best subarray is empty. The correct answer is -1 (the least-negative element).

Always initialize with the first element and start iterating from the second. This handles the all-negative case correctly without any special-case logic.

Best time to buy and sell stock

LeetCode 121, one of the most popular interview problems, gives you daily stock prices and asks you to find the maximum profit from a single buy-sell pair. This is Kadane's algorithm in disguise.

If you compute the array of daily price changes (today's price minus yesterday's price), then the maximum profit is exactly the maximum subarray sum of that difference array. A contiguous subarray of positive changes corresponds to buying at the start and selling at the end.

You can also solve it directly by tracking the minimum price seen so far and computing the profit at each day:

def maxProfit(prices):
    min_price = prices[0]
    max_profit = 0
    for price in prices[1:]:
        max_profit = max(max_profit, price - min_price)
        min_price = min(min_price, price)
    return max_profit

This is structurally identical to Kadane's. The running minimum plays the role of "the best starting point for a subarray," and price - min_price plays the role of "the current subarray sum." Same idea, different clothing.

Maximum product subarray

LeetCode 152 extends this idea: now the problem asks for the maximum product instead of the maximum sum. You might think you can just swap + for *, but there is a catch: multiplying two negative numbers gives a positive result. A very negative running product can become very positive if you hit another negative number.

The fix is to track both the running maximum and running minimum at each position. When you encounter a negative number, the max and min swap roles: what was the most negative becomes the most positive after multiplication:

def maxProduct(nums):
    cur_max = cur_min = best = nums[0]
    for num in nums[1:]:
        if num < 0:
            cur_max, cur_min = cur_min, cur_max
        cur_max = max(num, cur_max * num)
        cur_min = min(num, cur_min * num)
        best = max(best, cur_max)
    return best

This is the key insight: for additive Kadane's, a negative prefix is always bad, so you throw it away. For multiplicative Kadane's, a negative prefix might become good later, so you keep it around (as the minimum). The algorithm doubles in state from one variable to two, but the structure is the same.

Maximum subarray sum with circular wrap

For LeetCode 918, the array is circular, meaning the subarray can wrap around from the end to the beginning. For example, in [5, -3, 5], the best circular subarray is [5, 5] wrapping around, with sum 10.

The key observation is that a circular subarray that wraps around is the complement of a non-wrapping subarray in the middle. If the total sum of the array is S, and the minimum subarray sum (the "worst" contiguous section) is min_sub, then the best wrapping subarray has sum S - min_sub.

So the answer is max(kadane_max, total_sum - kadane_min), where kadane_max is standard Kadane's and kadane_min is Kadane's applied to find the minimum subarray. There is one edge case: if all elements are negative, total_sum - kadane_min is 0 (the empty subarray), which is wrong. In that case, just return kadane_max.

def maxSubarrayCircular(nums):
    total = 0
    cur_max = cur_min = best_max = best_min = nums[0]
    for num in nums[1:]:
        cur_max = max(num, cur_max + num)
        best_max = max(best_max, cur_max)
        cur_min = min(num, cur_min + num)
        best_min = min(best_min, cur_min)
        total += num
    total += nums[0]
    if best_max < 0:
        return best_max
    return max(best_max, total - best_min)

Complexity

Time is $O(n)$ for all variants: one pass through the array. Space is $O(1)$, just a handful of variables regardless of input size. This is optimal since you must read every element at least once.

Recognizing this pattern

You're probably looking at Kadane's when:

• The problem uses the word contiguous and asks for a maximum or minimum sum/product over a subarray.
• The subarray length is not fixed. If it were, you'd reach for a sliding window instead.
• You'd otherwise be tempted to compute every prefix sum pair in $O(n^2)$, but the constraints ($n \le 10^5$ or more) rule that out.
• You're tracking a running "best ending here" quantity that either extends the previous run or restarts at the current element.

Common templates:

• Classic max-sum: cur = max(num, cur + num); best = max(best, cur). Example: Maximum Subarray.
• Max-product variant: track both running max and running min because a negative flips signs. Example: Maximum Product Subarray.
• Circular Kadane: combine standard max with total - min to allow wraparound. Example: Maximum Sum Circular Subarray.
• Stock-trading disguise: single-pass Kadane on price differences. Example: Best Time to Buy and Sell Stock.
• K non-overlapping subarrays: extend Kadane with an extra dimension for how many segments you've used. Example: Maximum Sum of 3 Non-Overlapping Subarrays.