Kadane’s Algorithm: Maximum Subarray in O(N) + Edge Cases

Most Candidates Fail This Problem Because They Skip One Check

Here’s a claim: a significant portion of candidates who know Kadane’s algorithm still fail the maximum subarray problem in interviews. Not because they don’t understand the algorithm—they fail because they don’t handle an edge case that seems trivial until you’re staring at a wrong answer with 5 minutes left.

The edge case? An array of all negative numbers.

Kadane’s algorithm, in its textbook form, returns 0 for [-3, -1, -4]. But the correct answer is -1. And that single oversight has tanked more interviews than I’d like to guess.

The Brute Force Baseline: Why O(N²) Makes Sense First

Before optimizing, let me show you the brute force approach—not because you’d use it, but because it clarifies what we’re actually computing.

def max_subarray_bruteforce(nums: list[int]) -> int:
    """O(N²) baseline: check all subarrays"""
    if not nums:
        raise ValueError("Empty array has no subarrays")

    n = len(nums)
    max_sum = nums[0]  # Not 0! This is the first trap.

    for i in range(n):
        current_sum = 0
        for j in range(i, n):
            current_sum += nums[j]
            max_sum = max(max_sum, current_sum)

    return max_sum

# Quick sanity check
print(max_subarray_bruteforce([-3, -1, -4]))  # -1, not 0
print(max_subarray_bruteforce([1, -2, 3, 4]))  # 7

Notice max_sum = nums[0], not max_sum = 0. This is critical. If you initialize to 0, you’re implicitly allowing an empty subarray—which most problem statements explicitly forbid. The classic LeetCode 53 (Maximum Subarray) requires at least one element.

The brute force checks all $\frac{n(n+1)}{2}$ subarrays. For $n = 10,000$, that’s 50 million iterations. Kadane cuts this to exactly $n$.

Kadane’s Algorithm: The O(N) Insight

Joseph Kadane’s insight from 1984 is simple once you see it: at each position $i$, you have two choices—either extend the current subarray or start fresh from position $i$.

Mathematically, define $\text{current}[i]$ as the maximum subarray sum ending exactly at index $i$:

$$\text{current}[i] = \max(\text{nums}[i], \text{current}[i-1] + \text{nums}[i])$$

And the global maximum is simply:

$$\max_{i=0}^{n-1} \text{current}[i]$$

The recurrence says: “Do I gain by extending, or should I cut my losses?” When current[i-1] goes negative, you’re better off starting over.

The Implementation That Actually Works

Here’s the version that handles all edge cases. I’ll walk through why each line matters.

def max_subarray_kadane(nums: list[int]) -> int:
    """
    Kadane's algorithm with proper edge case handling.
    Returns maximum sum of contiguous subarray (at least 1 element).
    Time: O(N), Space: O(1)
    """
    if not nums:
        raise ValueError("Array must contain at least one element")

    # Initialize both to first element, NOT zero
    max_ending_here = nums[0]
    max_so_far = nums[0]

    # Start from index 1, not 0
    for i in range(1, len(nums)):
        # Either extend current subarray or start fresh
        max_ending_here = max(nums[i], max_ending_here + nums[i])
        max_so_far = max(max_so_far, max_ending_here)

    return max_so_far

The two critical decisions:

1. Initialize to nums[0], not 0. This ensures all-negative arrays return the largest negative.
2. Loop starts at index 1. We’ve already processed index 0 during initialization.

Let’s trace through [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

Index 0: max_ending_here = -2, max_so_far = -2
Index 1: max(-2 + 1, 1) = 1    → max_ending_here = 1, max_so_far = 1
Index 2: max(1 + -3, -3) = -2  → max_ending_here = -2, max_so_far = 1
Index 3: max(-2 + 4, 4) = 4    → max_ending_here = 4, max_so_far = 4
Index 4: max(4 + -1, -1) = 3   → max_ending_here = 3, max_so_far = 4
Index 5: max(3 + 2, 2) = 5     → max_ending_here = 5, max_so_far = 5
Index 6: max(5 + 1, 1) = 6     → max_ending_here = 6, max_so_far = 6
Index 7: max(6 + -5, -5) = 1   → max_ending_here = 1, max_so_far = 6
Index 8: max(1 + 4, 4) = 5     → max_ending_here = 5, max_so_far = 6

Final answer: 6 (subarray [4, -1, 2, 1])

See how at index 3, we reset? The cumulative sum had gone negative enough that starting fresh at 4 was better than carrying the baggage.

The All-Negative Trap: What Interviewers Actually Test

Let me show you the broken version that looks correct but isn’t:

# BROKEN: Common textbook implementation
def max_subarray_broken(nums):
    max_ending_here = 0  # BUG: should be nums[0]
    max_so_far = 0       # BUG: should be nums[0]

    for num in nums:
        max_ending_here = max(0, max_ending_here + num)
        max_so_far = max(max_so_far, max_ending_here)

    return max_so_far

print(max_subarray_broken([-3, -1, -4]))  # Returns 0, WRONG
print(max_subarray_broken([-1]))           # Returns 0, WRONG

This version treats negative running sums as “reset to 0.” That’s correct if you allow empty subarrays, but LeetCode 53 and most interview variants don’t.

Why do textbooks teach it this way? My best guess is that the original 1984 paper considered the “empty subarray” case valid. But modern problem statements almost always require at least one element. The CLRS textbook (Cormen et al.) uses the correct formulation, but many online tutorials don’t.

Returning the Subarray Itself: The Follow-Up Question

Interviewers love asking: “Now return the actual subarray, not just the sum.”

def max_subarray_with_indices(nums: list[int]) -> tuple[int, int, int]:
    """Returns (max_sum, start_index, end_index)"""
    if not nums:
        raise ValueError("Array must contain at least one element")

    max_ending_here = nums[0]
    max_so_far = nums[0]

    start = end = 0  # Final answer indices
    temp_start = 0   # Potential new start when we reset

    for i in range(1, len(nums)):
        # If starting fresh is better, update temp_start
        if nums[i] > max_ending_here + nums[i]:
            max_ending_here = nums[i]
            temp_start = i
        else:
            max_ending_here = max_ending_here + nums[i]

        # If we found a new global max, update final indices
        if max_ending_here > max_so_far:
            max_so_far = max_ending_here
            start = temp_start
            end = i

    return max_so_far, start, end

# Test
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
result, i, j = max_subarray_with_indices(nums)
print(f"Sum: {result}, Subarray: {nums[i:j+1]}")  
# Sum: 6, Subarray: [4, -1, 2, 1]

The trick is tracking temp_start—a candidate start index that only becomes official when we find a new global maximum. This adds no extra time complexity; still $O(n)$.

When Does Kadane Fail? The Divide-and-Conquer Alternative

Kadane’s algorithm assumes contiguous subarrays. What if the problem asks for the maximum sum of any subsequence (non-contiguous)? Kadane doesn’t apply. You’d just sum all positive numbers.

But there’s a legitimate alternative even for contiguous subarrays: divide-and-conquer, as presented in CLRS. It runs in $O(n \log n)$—worse than Kadane, but sometimes asked as a follow-up.

def max_crossing_sum(nums, left, mid, right):
    """Max subarray that crosses the midpoint"""
    # Left half, going backwards from mid
    left_sum = float('-inf')
    current = 0
    for i in range(mid, left - 1, -1):
        current += nums[i]
        left_sum = max(left_sum, current)

    # Right half, going forwards from mid+1
    right_sum = float('-inf')
    current = 0
    for i in range(mid + 1, right + 1):
        current += nums[i]
        right_sum = max(right_sum, current)

    return left_sum + right_sum

def max_subarray_dc(nums, left, right):
    """Divide and conquer: O(n log n)"""
    if left == right:
        return nums[left]

    mid = (left + right) // 2

    left_max = max_subarray_dc(nums, left, mid)
    right_max = max_subarray_dc(nums, mid + 1, right)
    cross_max = max_crossing_sum(nums, left, mid, right)

    return max(left_max, right_max, cross_max)

# Usage
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_dc(nums, 0, len(nums) - 1))  # 6

Why would you ever use this? Two reasons: (1) it demonstrates divide-and-conquer thinking, which interviewers test separately, and (2) it parallelizes well. On a system with $O(\log n)$ processors, the divide-and-conquer version runs in $O(n)$ parallel time.

But for a serial interview problem, just use Kadane.

Complexity Analysis: Beyond “It’s O(N)”

Time complexity is $O(n)$—one pass through the array, constant work per element.

Space complexity is $O(1)$—we only track two variables (max_ending_here, max_so_far).

But here’s what interviewers actually want to hear: “The recurrence $T(n) = T(n-1) + O(1)$ with base case $T(1) = O(1)$ gives $T(n) = O(n)$. We’re essentially computing a rolling maximum, which can’t be done faster than $O(n)$ since we must examine each element at least once.”

For space, the divide-and-conquer version uses $O(\log n)$ stack space due to recursion depth. Kadane’s iterative version is truly $O(1)$.

Related Problems: Pattern Recognition

Once you’ve internalized Kadane, these variations become straightforward:

The circular variant deserves a quick note: the maximum circular subarray is either (a) a regular contiguous subarray, or (b) wraps around, meaning the excluded middle portion is the minimum subarray. So you compute both and take the max—handling the all-negative edge case specially.

At this point, if you’re grinding through LeetCode at 2am, some Dark Chocolate Espresso Beans might keep you going. Debugging DP problems on caffeine and sugar is a rite of passage.

The Integer Overflow Trap

In Python, integers have arbitrary precision, so overflow isn’t a concern. But if you’re in C++, Java, or a whiteboard interview where the interviewer mentions “values up to $10^9$,” you need to watch for overflow.

With 32-bit signed integers (max $2^{31} – 1 \approx 2.1 \times 10^9$), an array of length DOLLAR_AMOUNT_2^5$ with values $10^5$each could sum to DOLLAR_AMOUNT_4^{10}$—overflow. Use long long in C++ or long in Java.

# Python handles this automatically
import sys
print(sys.maxsize)  # 9223372036854775807 on 64-bit
# But in Python, integers grow beyond even this

I haven’t personally hit this in a Python interview, but I’ve seen candidates lose points for not mentioning it when asked about edge cases.

What If the Interviewer Changes the Rules?

Some variations I’ve seen:

“What if we need exactly K elements?” — Kadane doesn’t directly apply. Use a sliding window of size K: sum the first K elements, then slide, adding the next and removing the first. Still $O(n)$.

“What if negative numbers aren’t allowed in the result?” — Filter to positive numbers first, then apply Kadane. If all numbers are negative, return the least negative (or 0 if empty subarrays are allowed).

“What if we want the second largest subarray sum?” — This is trickier. You’d need to track the second-best ending at each position, which gets into state management. Not a one-liner.

FAQ

Q: Does Kadane’s algorithm work for arrays with all zeros?

Yes, it returns 0 correctly since the maximum subarray (any single zero) has sum 0. The algorithm handles this naturally because max(0, 0 + 0) = 0 at every step.

Q: Why is the divide-and-conquer version O(n log n) instead of O(n)?

The recurrence is $T(n) = 2T(n/2) + O(n)$ because the crossing-sum calculation takes $O(n)$ time. By the Master Theorem, this gives $O(n \log n)$. Kadane avoids this by not splitting the problem at all.

Q: Can Kadane’s algorithm handle floating-point numbers?

Yes, with the usual floating-point caveats. The algorithm works identically, but be aware of precision issues when comparing sums. For numbers very close together, you might want an epsilon tolerance, though this rarely matters in practice.

When to Use What

Use Kadane’s algorithm for the standard maximum subarray problem—it’s optimal at $O(n)$ time and $O(1)$ space, and once you’ve got the edge case handling right, it’s nearly impossible to mess up.

Use divide-and-conquer if the interviewer explicitly asks for it, or if you’re showing off parallel algorithm design. Otherwise, it’s strictly worse.

The pattern I keep coming back to: Kadane is essentially asking “should I extend or restart?” at every position. That same question applies to maximum product subarray (track both max and min since negatives flip signs), and to some string problems too.

One thing I’m still unsure about: whether there’s a clean way to extend Kadane to 2D matrices without the $O(n^3)$ algorithm (fix left and right columns, reduce to 1D Kadane). I’ve seen papers claiming $O(n^2 \log n)$ using advanced data structures, but I haven’t implemented one that actually works. If anyone has a reference, I’d love to see it.