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

#kadanealgorithm #maximumsubarray #dynamicprogramming #codinginterview

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