Kadane's algorithm: two lines in the wrong order return 0 for [-3, -1, -2]

#algorithms #beginners #interview #python

Maximum subarray (LeetCode 53) is one of the most common interview warm-ups, and Kadane's algorithm solves it in one pass and constant space. It's also easy to write a version that passes the example in the problem statement and fails on an array of all-negative numbers. The difference is the order of two lines.

The idea

Walk the array while keeping a running sum of the subarray that ends at the current element. If that running sum ever drops below zero, throw it away: any later subarray is better off starting fresh than carrying a negative prefix. Along the way, remember the best sum you've seen.

The version that works

def max_subarray(nums):
    current = 0
    best = float('-inf')
    for x in nums:
        current += x
        best = max(best, current)   # 1. record the best
        if current < 0:             # 2. then discard a negative run
            current = 0
    return best

On [-2, 1, -3, 4, -1, 2, 1, -5, 4] it returns 6, from [4, -1, 2, 1]. On [-3, -1, -2] it returns -1, which is correct: the best subarray is the single element -1.

Two ways to break it

Reset before recording:

for x in nums:
    current += x
    if current < 0:
        current = 0
    best = max(best, current)       # sees 0, never the negative value

Start best at 0:

current, best = 0, 0

Both return 6 on the textbook example. Both return 0 on [-3, -1, -2] and on [-5]. There's no empty subarray to take, so 0 isn't an answer. Interviewers like all-negative input as a follow-up for exactly this reason.

The rule to remember: best has to see current before it's reset, and best has to start below any possible answer.

When Kadane isn't the right tool

Maximum product subarray (LeetCode 152). Two negatives multiply to a positive, so a negative running product can become the best one later. Discarding it is wrong; track both the running maximum and minimum product.
Circular arrays (LeetCode 918). The best subarray may wrap around. Take the larger of the ordinary maximum and total - minimum subarray, unless every element is negative.
A length limit. With "at most k elements", the reset rule no longer holds. Use prefix sums with a monotonic deque.

Seeing the two variables move

Most of Kadane's algorithm is in how current and best interact, and it's easier to see than to read. I built a free step-by-step Kadane's algorithm visualizer. You advance one element at a time and watch the running sum reset, with the matching code line highlighted in Python, Java, C++, JavaScript, TypeScript or C. Try an all-negative array and predict best before each step.

Disclosure: FaangPrep is my site. This lesson and the other introductory lessons open with no account; the other visualizers are free with an account, and the pattern courses are paid. This post was drafted with AI assistance and reviewed before publishing.

DEV Community