Leetcode 53. Maximum Subarray

Let's understand what we're being asked to do. We have an array like [-2, 1, -3, 4, -1, 2, 1, -5, 4] and need to find the contiguous subarray (elements that are next to each other) with the largest sum.

Tracing through: the subarray [4, -1, 2, 1] has sum 6, which is the maximum possible. Note that we can't skip elements - [4, 2, 1] wouldn't be valid because it's not contiguous.

Important constraint: We must pick at least one element (the subarray can't be empty).

Edge cases to consider: What if all numbers are negative? (pick the least negative one). What if the array has only one element? What if the entire array gives the maximum sum?

The brute force approach checks every possible contiguous subarray by using nested loops. The outer loop picks the starting index, the inner loop picks the ending index, and for each pair we calculate the sum of elements in that range. We track the maximum sum seen across all possible subarrays. This approach is straightforward but inefficient because it recalculates sums from scratch for overlapping subarrays.

def max_subarray_sum(nums):
    """
    Find the contiguous subarray with maximum sum using brute force.
    Check every possible subarray by trying all start and end positions.
    """
    if not nums:
        return 0
    
    max_sum = float('-inf')
    n = len(nums)
    
    # Outer loop: pick starting index
    for start in range(n):
        # Inner loop: pick ending index
        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]
            
            # Update maximum sum if current is larger
            if current_sum > max_sum:
                max_sum = current_sum
    
    return max_sum

At each position, we face a decision: should we extend the current subarray by including this element, or start a fresh subarray from this element?

If the sum we've built so far is negative, it will only drag down future elements - we're better off starting fresh!

By making this local decision at each step (extend vs. restart), we can find the global maximum in a single pass through the array.

This transforms what seems like a problem requiring checking all possible subarrays O(n²) into a linear O(n) solution by recognizing that negative accumulated sums are never worth keeping.

Imagine you're climbing a mountain range, tracking your altitude. At each step, you can either continue from your current altitude or reset to ground level.

If your current altitude is below ground (negative sum), you'd reset to ground level before continuing. You keep track of the highest point you've reached overall. This 'running sum with reset' pattern naturally finds the best contiguous segment.

Kadane's algorithm solves this in one pass by maintaining a running sum of the current subarray. At each element, we decide whether to extend the current subarray (add the element to our running sum) or start a new subarray from this element (if the running sum has become negative). We track the maximum sum seen so far across all positions. This greedy approach works because a negative running sum can never help maximize future subarrays, so we reset whenever it goes negative.

def max_subarray_sum(nums):
    """
    Find the contiguous subarray with the maximum sum using Kadane's algorithm.
    Time: O(n), Space: O(1)
    """
    # Initialize max_sum with first element (handles all-negative arrays)
    max_sum = nums[0]
    # Current running sum of subarray ending at current position
    current_sum = nums[0]
    
    # Iterate through array starting from second element
    for i in range(1, len(nums)):
        # Key decision: extend current subarray or start new one
        # If current_sum is negative, it can't help future sums, so reset
        current_sum = max(nums[i], current_sum + nums[i])
        
        # Update global maximum if current subarray sum is better
        max_sum = max(max_sum, current_sum)
    
    return max_sum

• Kadane's algorithm pattern: When you need to find an optimal contiguous subarray (maximum/minimum sum, product), think Kadane's algorithm - it works by making a local decision at each element (extend current subarray vs. start fresh) that leads to a global optimum, avoiding the O(n²) brute force of checking all subarrays.
• Local vs. global maximum tracking: Maintain two variables: current_sum (best subarray ending at current position) and max_sum (best seen so far). At each element, decide: `current_sum = max(nums[i], current_sum + nums[i])` - this captures whether adding the current element improves the running sum or if starting fresh is better.
• Greedy subarray extension principle: The key insight is that if your running sum becomes negative, it can never help future elements - discard it and restart. A negative prefix will only drag down any positive suffix, so the greedy choice to abandon it is always optimal.
• All-negative array edge case: A common mistake is initializing `max_sum = 0`, which fails when all numbers are negative (would return 0 instead of the least negative number). Always initialize `max_sum = nums[0]` or `float('-inf')` to handle arrays with only negative values correctly.
• O(n) time with O(1) space optimization: Unlike dynamic programming solutions that store results for each position in an array, Kadane's only needs the previous state to compute the next, achieving constant space complexity - this is a key pattern for optimizing DP solutions when you only reference the immediate previous result.
• Stock trading and time-series analysis: This pattern extends beyond coding interviews to financial analysis (maximum profit periods), signal processing (detecting strongest signal intervals), and resource allocation (identifying peak demand windows) - any domain where you need to find optimal consecutive time periods in sequential data.