Kadane's Algorithm: Maximum Subarray Sum

1. Introduction: The Power of Dropping Negativity

Imagine you are a day trader looking at the historical stock prices for a specific company, and you want to know the maximum profit you could have made if you bought and sold over a continuous period. Or, consider you are evaluating a sequence of financial returns, and you need to find the specific contiguous block of time that yielded the absolute highest net return.

This is the Maximum Subarray Problem: Given an array of integers (which can contain both positive and negative numbers), find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

The brute force way is to calculate the sum of every possible subarray. But what if the array has millions of data points? The brute force approach would take years. Enter Kadane’s Algorithm, an elegant, beautiful algorithm that solves this problem in a single pass ($O(N)$ time).

2. Core Concept: The "Local Maximum" Philosophy

At its heart, Kadane’s Algorithm is based on Dynamic Programming, specifically the idea of making a local decision at each step.

The Insight

As we iterate through the array, at any given element arr[i], we have exactly two choices for constructing a maximum subarray that ends at i:

1. Extend the existing subarray: Add arr[i] to the maximum subarray sum ending at arr[i-1].
2. Start a brand new subarray: The element arr[i] alone is better than appending it to the previous subarray.

When would we ever choose to start a new subarray? Only when the accumulated sum of the previous subarray becomes negative. If the sum of the elements before you is negative, adding that sum to your current element will mathematically only drag your current element down. You are better off ditching the past and starting fresh!

The Formula

Let current_max be the maximum subarray sum ending at the current index. Let global_max be the maximum subarray sum seen so far across the entire array.

For each element x in the array: $\text{current\_max} = \max(x, \text{current\_max} + x)$ $\text{global\_max} = \max(\text{global\_max}, \text{current\_max})$

3. Beginner Code Example: The Standard Approach

Let's look at the standard implementation of Kadane's Algorithm.

public class KadaneBasic {
    public static int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        
        // Initialize with the first element
        int currentMax = nums[0];
        int globalMax = nums[0];
        
        // Start iterating from the second element
        for (int i = 1; i < nums.length; i++) {
            // Do we extend the previous subarray, or start a new one?
            currentMax = Math.max(nums[i], currentMax + nums[i]);
            
            // Did this choice give us a new all-time high?
            globalMax = Math.max(globalMax, currentMax);
        }
        
        return globalMax;
    }

    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("Max Subarray Sum: " + maxSubArray(arr)); // Output: 6
    }
}

Step-by-Step Trace for [-2, 1, -3, 4, -1, 2, 1, -5, 4]

| Element | currentMax (max ending here) | globalMax (max seen so far) | Action Taken | | :--- | :--- | :--- | :--- | | -2 (init) | -2 | -2 | Initialize | | 1 | max(1, -2 + 1) = 1 | max(-2, 1) = 1 | Ditch past, start at 1 | | -3 | max(-3, 1 + -3) = -2 | max(1, -2) = 1 | Extend | | 4 | max(4, -2 + 4) = 4 | max(1, 4) = 4 | Ditch past, start at 4 | | -1 | max(-1, 4 - 1) = 3 | max(4, 3) = 4 | Extend | | 2 | max(2, 3 + 2) = 5 | max(4, 5) = 5 | Extend | | 1 | max(1, 5 + 1) = 6 | max(5, 6) = 6 | Extend | | -5 | max(-5, 6 - 5) = 1 | max(6, 1) = 6 | Extend | | 4 | max(4, 1 + 4) = 5 | max(6, 5) = 6 | Extend |

Result: globalMax is 6 (from subarray [4, -1, 2, 1]).

Complexity Analysis:

• Time Complexity: $O(N)$. We loop through the array exactly once, performing $O(1)$ operations per element.
• Space Complexity: $O(1)$. We only use two integer variables (currentMax, globalMax).

4. Intermediate Code Example: Returning the Subarray Indices

Often, interviews will ask you not just for the sum, but to actually print or return the subarray itself. We can modify Kadane's algorithm to track the start and end indices of the optimal subarray.

public class KadaneIndices {
    public static void printMaxSubarray(int[] nums) {
        int currentMax = nums[0];
        int globalMax = nums[0];
        
        int currentStart = 0;
        int bestStart = 0;
        int bestEnd = 0;
        
        for (int i = 1; i < nums.length; i++) {
            // If the current element alone is strictly greater than extending
            // the subarray, it means we must start a new subarray here.
            if (nums[i] > currentMax + nums[i]) {
                currentMax = nums[i];
                currentStart = i; // Move the start pointer to the current index
            } else {
                currentMax = currentMax + nums[i];
            }
            
            // If we found a new global maximum, update bestStart and bestEnd
            if (currentMax > globalMax) {
                globalMax = currentMax;
                bestStart = currentStart;
                bestEnd = i;
            }
        }
        
        System.out.println("Maximum Sum: " + globalMax);
        System.out.print("Subarray: [");
        for (int i = bestStart; i <= bestEnd; i++) {
            System.out.print(nums[i] + (i == bestEnd ? "" : ", "));
        }
        System.out.println("]");
    }
}

Time & Space: Still $O(N)$ time and $O(1)$ space. We merely added three integer variables to track indices.

5. Advanced Code Example: Maximum Circular Subarray

Problem Statement: (LeetCode 918) Given a circular integer array nums of length n, return the maximum possible sum of a non-empty subarray. A circular array means the end of the array wraps around to the beginning.

The Insight: A maximum circular subarray can take one of two forms:

1. Normal Case: The max subarray is standard and doesn't wrap around. (Kadane's handles this).
2. Wrap-around Case: The max subarray consists of a prefix of the array and a suffix of the array, leaving out a contiguous block in the middle.

Mathematically, the Wrap-around max sum is: Total_Array_Sum - Minimum_Subarray_Sum. Why? If you want the maximum sum that wraps around the edges, you want to remove the minimum contiguous subarray from the middle of the array!

public class KadaneCircular {
    public static int maxSubarraySumCircular(int[] nums) {
        int totalSum = 0;
        
        int currentMax = 0, globalMax = nums[0];
        int currentMin = 0, globalMin = nums[0];
        
        for (int x : nums) {
            // Calculate Total Sum
            totalSum += x;
            
            // Standard Kadane's for Max Subarray
            currentMax = Math.max(x, currentMax + x);
            globalMax = Math.max(globalMax, currentMax);
            
            // Reversed Kadane's for Min Subarray
            currentMin = Math.min(x, currentMin + x);
            globalMin = Math.min(globalMin, currentMin);
        }
        
        // Edge Case: If all elements are negative, globalMax is the max element.
        // However, totalSum - globalMin would be 0 (since globalMin would be the total sum).
        // A subarray MUST have at least one element, so we can't return an empty array sum of 0.
        if (globalMax < 0) {
            return globalMax;
        }
        
        // Return the max of normal case vs. wrap-around case
        return Math.max(globalMax, totalSum - globalMin);
    }
}

Complexity Analysis:

• Time Complexity: $O(N)$ - We iterate through the array precisely once, maintaining 5 variables.
• Space Complexity: $O(1)$ - Constant extra space used.

6. Common Mistakes Beginners Make

1. Initializing with 0 instead of nums[0]

   • The Mistake: int globalMax = 0;
   • Why it's wrong: If the array contains only negative numbers (e.g., [-5, -2, -9]), Kadane's will incorrectly return 0 because globalMax was initialized to 0.
   • The Fix: Always initialize globalMax and currentMax to the first element of the array.

2. Forgetting to update globalMax

   • The Mistake: Thinking currentMax at the end of the loop is the answer.
   • Why it's wrong: currentMax represents the max sum ending at the last element. The global maximum could have occurred anywhere in the middle of the array.

3. Overcomplicating the logic with inner loops

   • The Mistake: Writing a nested loop where the inner loop checks backwards to see if the sum increases.
   • Why it's wrong: That defeats the entire purpose of Kadane's $O(N)$ DP approach and regresses the algorithm to $O(N^2)$.

7. Interview Q&A

Q1: How do you prove Kadane’s algorithm is correct? Answer: By induction. Base case (array of size 1): the max subarray is the element itself. Inductive step: Assume we know the max subarray ending at index $i-1$. For index $i$, the contiguous max subarray ending at $i$ MUST either just be arr[i], or arr[i] appended to the max subarray ending at $i-1$. By calculating this correctly at every step, and keeping a running tally of the maximum seen across all steps, we guarantee we have checked every mathematically optimal endpoint in the array.

Q2: What is the Time and Space complexity of Kadane's? Can we do better? Answer: Time is $O(N)$ and Space is $O(1)$. We cannot do better than $O(N)$ time because any algorithm MUST look at every element in the array at least once to determine if its inclusion would change the maximum sum.

Q3: Can Kadane's Algorithm be parallelized? Answer: Standard Kadane’s is highly sequential because step $i$ strictly depends on step $i-1$. However, we can use a "Divide and Conquer" approach (like a Segment Tree) to solve the maximum subarray problem in parallel. The divide and conquer approach takes $O(N)$ time but allows $O(\log N)$ parallel time by merging left and right halves.

Q4: (LeetCode 152) Maximum Product Subarray: Can we use Kadane's for products? Answer: Yes, but with a twist. Because multiplying two negative numbers yields a positive number, a very small negative running product can instantly become a massive positive product if multiplied by another negative. Therefore, we must maintain both currentMax and currentMin at each step.

8. Practice Problems

1. Maximum Subarray (LeetCode 53)
   • Goal: Implement standard Kadane's algorithm.
2. Maximum Product Subarray (LeetCode 152)
   • Hint: Modify Kadane's to keep track of the minimum product as well as the maximum product.
3. Maximum Alternating Subsequence Sum (LeetCode 1911)
   • Hint: This is a DP problem closely related to the local-decision philosophy of Kadane's. Keep track of the max sum ending on an even index vs an odd index.

9. Summary

• Problem Solved: Finding the contiguous subarray with the maximum sum.
• The Core Idea: A negative running sum will only drag down future elements. When your running sum drops below zero, reset it.
• Time Complexity: $O(N)$ — achieved by making a local $O(1)$ decision at each step.
• Space Complexity: $O(1)$ — achieved by keeping track of only the current and global maximums instead of storing a full DP table.
• Adaptability: Kadane's philosophy can be adapted to circular arrays, finding subarray boundaries, and finding maximum products.