Kadane's Algorithm

Before we start

This pattern sits right at the boundary between arrays and dynamic programming — it is often the first DP idea students encounter without realising it. By the end of this page you will be able to:

• See Kadane's algorithm as a decision made at every position: "extend the previous chain or start fresh?"
• Explain out loud why you only ever need to remember one number, not the whole history.
• Recognise the pattern and apply it to the circular variant — the classic interview hard follow-up.

Stop at every Pause & Think box. The decision logic there is the entire algorithm.

Picture this first (no code yet)

Day:  1     2     3     4     5     6     7     8     9
     +3    -1    +4    +1    -5    +9    +2    -6    +5

The actual problem

Given an integer array that may contain both positive and negative numbers, find the contiguous subarray with the largest sum. Return that sum.

nums   = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
answer =  6          (subarray [4, -1, 2, 1])

The array can have all negatives — in that case the best subarray is a single element (the least negative one).

First, the slow way (so you feel the pain)

The brute-force: try every possible subarray.

def max_subarray_slow(nums):
    n = len(nums)
    best = float('-inf')
    for i in range(n):
        total = 0
        for j in range(i, n):
            total += nums[j]
            best = max(best, total)
    return best

For every start index i, you extend to every end index j. That's roughly n²/2 subarrays:

n = 1,000      →  ~500,000 pairs
n = 100,000    →  ~5,000,000,000 pairs  (five billion — too slow)

Kadane's does this in a single pass.

The turning point

You should extend when prev > 0 — adding prev makes nums[i] larger. You should start fresh when prev ≤ 0 — the previous chain drags you down; just take nums[i] alone.

In code: current = max(nums[i], prev + nums[i]).

But max(a, a + prev) chooses a when prev ≤ 0 and a + prev when prev > 0 — which is exactly max(nums[i], current + nums[i]).

And the global best is the maximum current seen across all positions.

The one idea to remember

You only ever need to remember one number — the best sum ending at the current position. No need to store the entire history.

Watch it happen, frame by frame

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

i=0: nums[0]=-2.  current = max(-2,  0 + (-2)) = -2.  global_best = -2
i=1: nums[1]=1.   current = max( 1, -2 +   1 ) =  1.  global_best =  1
i=2: nums[2]=-3.  current = max(-3,  1 + (-3)) = -2.  global_best =  1
i=3: nums[3]=4.   current = max( 4, -2 +   4 ) =  4.  global_best =  4
i=4: nums[4]=-1.  current = max(-1,  4 + (-1)) =  3.  global_best =  4
i=5: nums[5]=2.   current = max( 2,  3 +   2 ) =  5.  global_best =  5
i=6: nums[6]=1.   current = max( 1,  5 +   1 ) =  6.  global_best =  6
i=7: nums[7]=-5.  current = max(-5,  6 + (-5)) =  1.  global_best =  6
i=8: nums[8]=4.   current = max( 4,  1 +   4 ) =  5.  global_best =  6

Answer: 6  ✅  (subarray [4,-1,2,1] from index 3 to 6)

Notice that at i=3, current resets effectively to 4 — the previous chain was -2 (negative), so starting fresh at +4 beats extending. That is the "start fresh" decision in action.

i=0: current = max(-1, -inf + (-1)) = -1.  global_best = -1
i=1: current = max(-2, -1 + (-2))  = -2.  global_best = -1
i=2: current = max(-3, -2 + (-3))  = -3.  global_best = -1
i=3: current = max(-4, -3 + (-4))  = -4.  global_best = -1

Answer: -1  ✅

Now, the code — line by line

def maxSubArray(nums):
    current = nums[0]          # best sum of a subarray ending at the current position
    global_best = nums[0]      # best sum seen anywhere so far

    for i in range(1, len(nums)):
        current = max(nums[i], current + nums[i])   # extend or start fresh
        global_best = max(global_best, current)     # update the global champion

    return global_best

Mapping to the portfolio story:

• current = nums[0] — "Start on day 1; the streak is just that day."
• max(nums[i], current + nums[i]) — "Is it better to continue the streak, or cut losses and start a new one today?"
• global_best = max(global_best, current) — "Record today's streak if it's the best we've ever seen."
• The loop runs from index 1 — we already handled index 0 as the initial state.

Why initialise with nums[0] and not 0?

If we initialised current = 0, we'd allow the "empty subarray" (sum = 0) as a candidate. But the problem requires at least one element. Initialising with nums[0] guarantees at least the first element is included, and the loop handles the rest.

Why does it never miss the best subarray?

Claim: After processing index i, current holds the maximum sum of any subarray ending exactly at index i.

Proof by induction:

• Base: i = 0. The only subarray ending at 0 is [nums[0]]. current = nums[0]. ✓
• Step: Assume true for i-1. Any subarray ending at i either:
  • consists of nums[i] alone (sum = nums[i]), or
  • extends the best subarray ending at i-1 (sum = current_prev + nums[i]).
  • max(nums[i], current_prev + nums[i]) is the larger of the two. ✓

global_best takes the maximum of all these, so it equals the maximum over all (start, end) pairs — which is the answer. □

Why is it so fast?

One pass through the array. One comparison per element. No inner loops, no storing past subarrays.

When should I reach for this? (the trigger list)

Reach for Kadane's when you notice:

• The problem asks for the maximum (or minimum) sum subarray.
• The array has both positive and negative numbers — otherwise the answer is trivially the whole array.
• You see phrases like "contiguous subarray," "consecutive sequence," "best run."
• The brute force involves a double loop to check all subarrays.
• There's a circular variant (see below) — this is the classic extension.

Also recognise it in disguise: if "subarray" is replaced by "substring" (of integers), same pattern.

The same trick in four disguises

Disguise 1 — Maximum Product Subarray (LC #152)

Instead of sum, maximise the product. But products have a twist: a large negative number becomes a large positive when multiplied by another negative. So you must track both the current maximum and current minimum at each step.

def maxProduct(nums):
    cur_max = cur_min = global_best = nums[0]

    for x in nums[1:]:
        candidates = (x, cur_max * x, cur_min * x)
        cur_max = max(candidates)          # a big negative × negative might be the new max
        cur_min = min(candidates)          # track minimum for future sign flips
        global_best = max(global_best, cur_max)

    return global_best

The "extend or start fresh" decision is the same; you just carry two running values instead of one.

Disguise 2 — Maximum Circular Subarray (LC #918)

The array is circular — the subarray can wrap around from the end back to the beginning.

Key insight: A circular maximum subarray is either:

1. A normal (non-wrapping) subarray → use Kadane's directly.
2. A wrapping subarray → the elements it excludes form a contiguous block in the middle → their sum is minimised → the answer is total_sum − min_subarray_sum (run Kadane's on negated values).

def maxSubarraySumCircular(nums):
    total = sum(nums)

    # Case 1: standard Kadane's for non-circular max
    cur = best_max = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)
        best_max = max(best_max, cur)

    # Case 2: total - minimum subarray sum (circular wrap)
    cur = best_min = nums[0]
    for x in nums[1:]:
        cur = min(x, cur + x)
        best_min = min(best_min, cur)

    # If all numbers are negative, best_min == total (entire array), giving total - total = 0
    # which is wrong (empty subarray). In that case, case 1 gives the correct answer.
    if best_min == total:
        return best_max

    return max(best_max, total - best_min)

Disguise 3 — Maximum Sum of Non-adjacent Elements

Not a Kadane variant, but looks similar. Track two states: "best including current" and "best excluding current." The underlying idea — carry forward a running decision — is the same spirit.

Disguise 4 — Stock Buy and Sell (LC #121)

Maximum profit = maximum of prices[j] - prices[i] for j > i. This is the maximum subarray problem in disguise, where the "array" is the day-over-day differences [prices[1]-prices[0], prices[2]-prices[1], ...]. Run Kadane's on those differences.

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

The min_price tracking is equivalent to "extending or restarting" based on the most advantageous buy point.

Traps that catch beginners

Say it like a pro (interview one-liner)

"I'll use Kadane's algorithm — a single pass that decides at each position whether to extend the previous subarray or start fresh. The decision is simply: is the running sum still positive? If yes, extend; if not, restart. I track the global best as I go. O(n) time, O(1) space."

For the circular variant, add:

"For the circular case, the answer is either a normal max subarray or the total minus the minimum subarray in the middle. I run Kadane's twice — once for max, once for min on the same array."

Check yourself

Practice problems

Next up: Moore's Voting Algorithm, where a single clever cancellation trick finds the majority element in O(n) time and O(1) space — with no hashing, no sorting, and no counting.