Algo: Maximum Subarray Sum (Kadane's Algorithm)

Finding the largest possible sum of a contiguous sequence within an array is a fundamental problem in algorithm design, with real-world applications ranging from analyzing stock price fluctuations to identifying regions of interest in genomic data. Kadane's algorithm provides an elegant and optimal $O(n)$ solution to this maximum subarray sum problem, demonstrating the power of dynamic programming thinking. Understanding this algorithm is essential for any engineer or developer working with sequence data, as it forms the basis for more complex optimizations.

Understanding the Dynamic Programming Insight

The core challenge is straightforward: given an array of integers (which can be positive, negative, or zero), you must find the contiguous subarray that has the greatest sum. A brute-force approach would check every possible start and end index, leading to an $O(n^3)$ or $O(n^2)$ time complexity, which is impractical for large datasets. Kadane's algorithm employs a dynamic programming strategy to build the solution incrementally.

The key insight is to consider, at each position in the array, the best you can do ending at that exact position. Define a state current_max that represents the maximum sum of a contiguous subarray that must end at the current index i. For the next element, you have only two choices: either start a new subarray at i, or extend the best subarray ending at i-1. Therefore, the recurrence relation is: current_max = max(nums[i], current_max + nums[i]). You simultaneously maintain a global_max variable that tracks the maximum current_max value seen so far. This elegant logic ensures that every element is processed exactly once, resulting in linear $O(n)$ time and constant $O(1)$ space.

Consider the array [-2, 1, -3, 4, -1, 2, 1, -5, 4]. Walking through Kadane's algorithm:

• At index 0 (-2): current_max = -2, global_max = -2.
• At index 1 (1): current_max = max(1, -2 + 1) = 1. Starting fresh is better. global_max = max(-2, 1) = 1.
• At index 2 (-3): current_max = max(-3, 1 + (-3)) = -2. global_max stays 1.
• At index 3 (4): current_max = max(4, -2 + 4) = 4. Start fresh. global_max = 4.
• This process continues, with global_max finally becoming 6 for the subarray [4, -1, 2, 1].

Implementation and Critical Edge Cases

Translating the insight into code is concise. The basic implementation initializes current_max and global_max to the first element, then iterates from the second element onward.

def kadane(nums):
    if not nums:
        return 0
    current_max = global_max = nums[0]
    for num in nums[1:]:
        current_max = max(num, current_max + num)
        global_max = max(global_max, current_max)
    return global_max

A critical edge case is an array where all elements are negative, e.g., [-3, -5, -2]. The correct answer should be -2 (the largest single element), not 0. The algorithm above handles this correctly because current_max will always be the current number itself (since adding a more negative current_max would make it worse), and global_max will track the highest single value. A common mistake is initializing current_max = global_max = 0, which would erroneously return 0 for an all-negative array. Always initialize with the first array element to guarantee correctness for all inputs.

Extending the Algorithm: Boundaries and Higher Dimensions

Often, you need to identify the actual subarray indices, not just the sum. This requires extending Kadane's algorithm to track the starting and ending positions. You maintain additional variables: start_temp for the temporary start of the current best subarray ending at i, and start/end for the global best subarray.

def kadane_with_indices(nums):
    global_max = current_max = nums[0]
    global_start = global_end = 0
    temp_start = 0

    for i in range(1, len(nums)):
        if nums[i] > current_max + nums[i]:
            current_max = nums[i]
            temp_start = i
        else:
            current_max = current_max + nums[i]

        if current_max > global_max:
            global_max = current_max
            global_start = temp_start
            global_end = i
    return global_max, global_start, global_end

The logic can also be scaled to solve the 2D maximum subarray problem, where you must find the rectangular submatrix with the largest sum in a 2D array. The technique involves fixing the top and bottom rows of the potential rectangle and compressing the columns between them into a 1D array of cumulative sums. You then apply Kadane's algorithm to this compressed array to find the best left and right columns. By iterating over all possible top and bottom rows, you solve the problem in $O(n^3)$ time for an $n$ x $n$ matrix, which is far superior to the brute-force $O(n^4)$.

Algorithmic Trade-offs: Kadane vs. Divide-and-Conquer

Kadane's algorithm is not the only way to solve the maximum subarray problem. A divide-and-conquer approach recursively splits the array into halves, finds the maximum sum in the left half, the right half, and a subarray crossing the midpoint, and combines the results. This method has a time complexity of $O(n\log n)$.

The comparison is instructive. Divide-and-conquer is more general and teaches important recursive design principles, but it is asymptotically slower than Kadane's $O(n)$ and uses $O(\log n)$ recursive stack space. Kadane's algorithm is a classic example of how dynamic programming can optimize a problem by identifying an optimal substructure and overlapping subproblems—here, the subproblem is "the maximum subarray ending at index i." For practical purposes, Kadane's linear-time, constant-space solution is almost always the preferred choice. The divide-and-conquer version remains valuable for educational contexts and as a stepping stone to parallel algorithms, where the independent halves can be processed concurrently.

Common Pitfalls

1. Incorrect Initialization for All-Negative Arrays: As discussed, setting current_max = global_max = 0 fails. Always initialize with the first element of the array to cover this edge case automatically.
2. Confusing the Running Sum with the Global Sum: It's crucial to understand that current_max is the best sum ending at the current index, while global_max is the best sum found anywhere so far. Forgetting to update global_max independently will yield incorrect results.
3. Off-by-One Errors When Tracking Indices: When extending the algorithm to find subarray boundaries, carefully manage when to reset the temporary start index. It should only reset when you choose the current element alone over extending the previous subarray.
4. Misapplying to 2D Without Compression: Attempting to directly adapt the 1D logic to a 2D grid will not work. You must remember the core reduction step: fixing two rows and using prefix sums to create a 1D array for Kadane's algorithm to process.

Summary

• Kadane's algorithm solves the maximum subarray sum problem in optimal $O(n)$ time by using a dynamic programming state that tracks the best sum ending at each position.
• The implementation is concise but must be initialized with the first array element to correctly handle all-negative arrays, where the answer is the largest single element.
• The algorithm can be extended to record the starting and ending indices of the maximum subarray by managing additional pointer variables.
• For the 2D maximum subarray problem, the solution involves reducing the problem to 1D by fixing rows and compressing columns, then applying Kadane's algorithm, yielding an $O(n^3)$ solution.
• Compared to the $O(n\log n)$ divide-and-conquer approach, Kadane's algorithm is faster and simpler, showcasing the practical advantage of dynamic programming for this specific optimal substructure.