Maximum Subarray Sum: Kadane's Algorithm

Key Insights

Kadane’s algorithm solves the maximum subarray problem in O(n) time and O(1) space by making a simple decision at each element: extend the current subarray or start fresh.
The core insight is that a negative running sum never helps—if your accumulated sum drops below zero, any future subarray is better off starting from the next element.
This algorithm appears constantly in interviews and has direct applications in finance (maximum profit periods), signal processing (strongest signal segments), and image processing (brightest regions).

The Maximum Subarray Problem

Given an array of integers, find the contiguous subarray with the largest sum. That’s it. Simple to state, but the naive solution is painfully slow.

Consider this array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

The maximum subarray is [4, -1, 2, 1] with a sum of 6. Finding this efficiently is the challenge.

This problem shows up everywhere. In finance, you’re looking for the best period to have held a stock. In signal processing, you want the segment with the strongest cumulative signal. In bioinformatics, you’re identifying regions of DNA with the highest scores. The pattern is universal: find the best contiguous segment.

Why Brute Force Fails

The obvious approach is to check every possible subarray. With two nested loops, you can generate all start and end positions, then sum each subarray.

def max_subarray_brute_force_n3(nums: list[int]) -> int:
    """O(n³) brute force - checks every subarray."""
    if not nums:
        return 0
    
    max_sum = float('-inf')
    n = len(nums)
    
    for start in range(n):
        for end in range(start, n):
            # Calculate sum of subarray from start to end
            current_sum = 0
            for k in range(start, end + 1):
                current_sum += nums[k]
            max_sum = max(max_sum, current_sum)
    
    return max_sum

This runs in O(n³) time. We can optimize to O(n²) by maintaining a running sum:

def max_subarray_brute_force_n2(nums: list[int]) -> int:
    """O(n²) brute force - maintains running sum."""
    if not nums:
        return 0
    
    max_sum = float('-inf')
    n = len(nums)
    
    for start in range(n):
        current_sum = 0
        for end in range(start, n):
            current_sum += nums[end]
            max_sum = max(max_sum, current_sum)
    
    return max_sum

Still too slow. For an array of 100,000 elements, O(n²) means 10 billion operations. In competitive programming or production systems processing real-time data, this is unacceptable.

Kadane’s Algorithm: The Key Insight

Jay Kadane’s algorithm, published in 1984, solves this in O(n) time with O(1) space. The insight is elegant: at each position, you make exactly one decision.

Should I extend the current subarray, or start a new one here?

The answer depends on whether the current running sum helps or hurts. If your running sum is negative, it can only drag down any future elements. Throw it away and start fresh.

Here’s the logic:

Track two values: current_max (best sum ending at current position) and global_max (best sum seen anywhere)
At each element, current_max = max(nums[i], current_max + nums[i])
Update global_max if current_max is larger

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

Index	Value	current_max	global_max	Decision
0	-2	-2	-2	Start with -2
1	1	1	1	Restart (1 > -2+1)
2	-3	-2	1	Extend (1-3 > -3)
3	4	4	4	Restart (4 > -2+4)
4	-1	3	4	Extend (4-1 > -1)
5	2	5	5	Extend (3+2 > 2)
6	1	6	6	Extend (5+1 > 1)
7	-5	1	6	Extend (6-5 > -5)
8	4	5	6	Extend (1+4 > 4)

Final answer: 6.

def kadane(nums: list[int]) -> int:
    """Kadane's algorithm - O(n) time, O(1) space."""
    if not nums:
        return 0
    
    current_max = nums[0]
    global_max = nums[0]
    
    for i in range(1, len(nums)):
        # Key decision: extend current subarray or start new one
        current_max = max(nums[i], current_max + nums[i])
        global_max = max(global_max, current_max)
    
    return global_max

That’s the entire algorithm. Five lines of logic.

Handling Edge Cases

Production code needs to handle edge cases gracefully. Here’s a robust implementation:

def kadane_robust(nums: list[int]) -> int:
    """Kadane's algorithm with comprehensive edge case handling."""
    # Edge case: empty array
    if not nums:
        raise ValueError("Array cannot be empty")
    
    # Edge case: single element
    if len(nums) == 1:
        return nums[0]
    
    current_max = nums[0]
    global_max = nums[0]
    
    for i in range(1, len(nums)):
        current_max = max(nums[i], current_max + nums[i])
        global_max = max(global_max, current_max)
    
    return global_max


# Test edge cases
print(kadane_robust([-1]))           # -1 (single negative)
print(kadane_robust([-3, -1, -2]))   # -1 (all negative, pick least bad)
print(kadane_robust([5]))            # 5 (single positive)
print(kadane_robust([1, 2, 3, 4]))   # 10 (all positive, take everything)

The all-negative case is worth noting. Kadane’s algorithm correctly returns the least negative number (the “maximum” subarray). Some problem variants ask for 0 when all elements are negative—read requirements carefully.

Tracking Subarray Indices

Often you need the actual subarray, not just its sum. Track where the current subarray started and update the result indices when you find a new global maximum:

def kadane_with_indices(nums: list[int]) -> tuple[int, int, int]:
    """Returns (max_sum, start_index, end_index)."""
    if not nums:
        raise ValueError("Array cannot be empty")
    
    current_max = nums[0]
    global_max = nums[0]
    
    # Track current subarray start and result indices
    current_start = 0
    result_start = 0
    result_end = 0
    
    for i in range(1, len(nums)):
        # If starting fresh is better, update current_start
        if nums[i] > current_max + nums[i]:
            current_max = nums[i]
            current_start = i
        else:
            current_max = current_max + nums[i]
        
        # Update result if we found a new global maximum
        if current_max > global_max:
            global_max = current_max
            result_start = current_start
            result_end = i
    
    return global_max, result_start, result_end


# Example usage
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max_sum, start, end = kadane_with_indices(nums)
print(f"Max sum: {max_sum}")           # 6
print(f"Subarray: {nums[start:end+1]}") # [4, -1, 2, 1]

The Circular Array Variant

What if the array is circular, meaning the subarray can wrap around? This is LeetCode problem #918.

The insight: the maximum circular subarray is either:

A normal subarray (use standard Kadane’s), or
A wraparound subarray, which means the middle portion we’re excluding is the minimum subarray

For case 2, the answer is total_sum - min_subarray_sum.

def max_subarray_circular(nums: list[int]) -> int:
    """Maximum subarray sum in a circular array."""
    if not nums:
        return 0
    
    # Standard Kadane's for max subarray
    current_max = global_max = nums[0]
    # Inverted Kadane's for min subarray
    current_min = global_min = nums[0]
    total = nums[0]
    
    for i in range(1, len(nums)):
        total += nums[i]
        
        current_max = max(nums[i], current_max + nums[i])
        global_max = max(global_max, current_max)
        
        current_min = min(nums[i], current_min + nums[i])
        global_min = min(global_min, current_min)
    
    # Edge case: all negative (global_min == total means we'd take nothing)
    if global_min == total:
        return global_max
    
    return max(global_max, total - global_min)

Complexity Analysis

Approach	Time	Space	Notes
Brute Force (triple loop)	O(n³)	O(1)	Never use this
Brute Force (running sum)	O(n²)	O(1)	Still too slow
Divide and Conquer	O(n log n)	O(log n)	Elegant but unnecessary
Kadane’s Algorithm	O(n)	O(1)	Optimal

Kadane’s is optimal. You must examine each element at least once, so O(n) is the theoretical lower bound. You can’t do better.

Solving LeetCode #53

This is the classic maximum subarray problem. Here’s a clean, interview-ready solution:

class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        """
        LeetCode 53: Maximum Subarray
        
        Kadane's algorithm - at each position, decide whether to
        extend the current subarray or start a new one.
        
        Time: O(n), Space: O(1)
        """
        current = global_max = nums[0]
        
        for num in nums[1:]:
            current = max(num, current + num)
            global_max = max(global_max, current)
        
        return global_max

In interviews, explain your thought process: “I’m tracking the best sum ending at each position. If the running sum goes negative, I restart because a negative prefix can only hurt future sums.”

Stock Profit Connection

The maximum subarray problem is equivalent to finding the maximum profit from a single buy-sell transaction. Convert prices to daily changes, then apply Kadane’s:

def max_profit(prices: list[int]) -> int:
    """Maximum profit from one buy-sell transaction."""
    if len(prices) < 2:
        return 0
    
    # Convert to daily changes
    changes = [prices[i] - prices[i-1] for i in range(1, len(prices))]
    
    # Apply Kadane's (but floor at 0 since we can choose not to trade)
    current = global_max = 0
    for change in changes:
        current = max(0, current + change)
        global_max = max(global_max, current)
    
    return global_max

This is LeetCode #121 (Best Time to Buy and Sell Stock). The connection isn’t immediately obvious, but once you see it, you’ll never forget it.

Final Thoughts

Kadane’s algorithm is a masterclass in dynamic programming intuition. The problem seems to require examining all subarrays, but by recognizing that negative running sums are never useful, we reduce O(n²) to O(n).

Master this pattern. It appears in countless variations: 2D maximum submatrix (apply Kadane’s to compressed columns), maximum product subarray (track both max and min), and circular arrays. The core insight—extend or restart—transfers directly.

When you see “maximum contiguous” in an interview, Kadane’s should be your first thought.