LeetCode 53: Maximum Subarray - All Approaches Explained

Problem Statement

The Maximum Subarray problem, LeetCode 53, is a medium-difficulty challenge where you’re given an integer array nums. Your task is to find the contiguous subarray (containing at least one number) that has the largest sum and return that sum. This is a classic problem known as Kadane’s Algorithm in computer science.

Constraints

1 ≤ nums.length ≤ 10⁵.
-10⁴ ≤ nums[i] ≤ 10⁴.

Example

Example in Python

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum = 6.

Example in Python

004aad

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum = 1.

004aad

Example in Python

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] (entire array) has the largest sum = 23.

Understanding the Problem

We need to find the contiguous subarray with the maximum sum. Key points:

The subarray must be contiguous (no gaps).
It must contain at least one element.
The array can have positive, negative, or mixed numbers.
A brute-force approach would check all subarrays, but we can optimize this. Let’s explore three approaches:

Brute Force : Check all possible subarrays.
Divide and Conquer : Split and solve recursively.
Kadane’s Algorithm : Linear scan (best approach).

Approach 1: Brute Force

Intuition

Calculate the sum of every possible contiguous subarray and track the maximum sum encountered.

How It Works

Use two nested loops:
- Outer loop: Start index.
- Inner loop: End index.
Compute the sum for each subarray and update the maximum.

Step-by-Step Example

For nums = [-2,1,-3,4]:

[-2] = -2.
[-2,1] = -1.
[-2,1,-3] = -4.
[-2,1,-3,4] = 0.
[1] = 1.
[1,-3] = -2.
[1,-3,4] = 2.
[-3] = -3.
[-3,4] = 1.
[4] = 4.
Max sum = 4.

004aad Python Code

Example in Python

def maxSubArray_brute_force(nums):
    max_sum = float('-inf')
    n = len(nums)
    
    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

# Test cases
print(maxSubArray_brute_force([-2,1,-3,4,-1,2,1,-5,4]))  # Output: 6
print(maxSubArray_brute_force([1]))                      # Output: 1
print(maxSubArray_brute_force([5,4,-1,7,8]))            # Output: 23

Detailed Walkthrough

Loops : i=0 to n-1, j=i to n-1.
For [1]: Single subarray [1], max = 1.
Checks all possibilities exhaustively.

Complexity

Time Complexity : O(n²). Two nested loops.
Space Complexity : O(1). Only stores max_sum and current_sum.

Pros and Cons

Pros : Simple, guaranteed correct.
Cons : Too slow for large arrays.

Approach 2: Divide and Conquer

Intuition

Divide the array into two halves, recursively find the maximum subarray sum in each half, and also consider subarrays crossing the midpoint. Combine these results to get the overall maximum.

How It Works

Recursively split the array into left and right halves.
Compute:
- Max sum in left half.
- Max sum in right half.
- Max sum crossing the middle (left-to-mid + mid-to-right).
Return the maximum of these three.

Step-by-Step Example

For nums = [-2,1,-3,4]:

Split: [-2,1] and [-3,4].004aad
Left: [-2,1] → max(1) via [-2], [-2,1], [1].
Right: [-3,4] → max(4) via [-3], [-3,4], [4].
Cross: Mid=1, max left from 1 = 1, max right from 2 = 4, total = 2.
Max(1, 4, 2) = 4.

Python Code

Example in Python

def maxSubArray_divide_conquer(nums):
    def max_crossing_sum(nums, left, mid, right):
        left_sum = float('-inf')
        current_sum = 0
        for i in range(mid, left - 1, -1):
            current_sum += nums[i]
            left_sum = max(left_sum, current_sum)
        
        right_sum = float('-inf')
        current_sum = 0
        for i in range(mid + 1, right + 1):
            current_sum += nums[i]
            right_sum = max(right_sum, current_sum)
        
        return left_sum + right_sum
    
    def helper(nums, left, right):
        if left == right:
            return nums[left]
        
        mid = (left + right) // 2
        return max(helper(nums, left, mid),         # Left half
                  helper(nums, mid + 1, right),    # Right half
                  max_crossing_sum(nums, left, mid, right))  # Crossing
    
    return helper(nums, 0, len(nums) - 1)

# Test cases
print(maxSubArray_divide_conquer([-2,1,-3,4,-1,2,1,-5,4]))  # Output: 6
print(maxSubArray_divide_conquer([1]))                      # Output: 1
print(maxSubArray_divide_conquer([5,4,-1,7,8]))            # Output: 23

Detailed Walkthrough

Recursion : Splits until single elements.
Crossing : Computes max sum spanning mid.
For [5,4,-1,7,8]: Entire array = 23 (best case).

Complexity

Time Complexity : O(n log n). Divides into log n levels, O(n) work per level.
Space Complexity : O(log n). Recursion stack depth.

Pros and Cons

Pros : More efficient than brute force, educational.
Cons : Still slower than linear, complex to implement.

Approach 3: Kadane’s Algorithm (Best Approach)

Intuition

Use a greedy approach to scan the array once, maintaining the maximum sum ending at the current position and the overall maximum sum seen so far. If the current sum becomes negative, reset it, as it won’t contribute to a larger sum. This is the best approach because it’s O(n) time, simple, and optimal.

How It Works

Track max_so_far (global max) and max_ending_here (local max).
For each element:
- Update max_ending_here as max(current element, previous sum + current).
- Update max_so_far if max_ending_here is larger.
Return max_so_far.

Step-by-Step Example

For nums = [-2,1,-3,4,-1,2,1,-5,4]:

i=0: max_ending_here=-2, max_so_far=-2.
i=1: max_ending_here=1, max_so_far=1.
i=2: max_ending_here=-2, max_so_far=1.
i=3: max_ending_here=4, max_so_far=4.
i=4: max_ending_here=3, max_so_far=4.
i=5: max_ending_here=5, max_so_far=5.
i=6: max_ending_here=6, max_so_far=6.
i=7: max_ending_here=1, max_so_far=6.
i=8: max_ending_here=5, max_so_far=6.
Result: 6.

Python Code (Best Approach)

Example in Python

def maxSubArray(nums):
    max_so_far = nums[0]
    max_ending_here = nums[0]
    
    for i in range(1, len(nums)):
        max_ending_here = max(nums[i], max_ending_here + nums[i])
        max_so_far = max(max_so_far, max_ending_here)
    
    return max_so_far

# Test cases
print(maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))  # Output: 6
print(maxSubArray([1]))                      # Output: 1
print(maxSubArray([5,4,-1,7,8]))            # Output: 23

Detailed Walkthrough

Greedy : Resets when sum goes negative.
For [1]: max_so_far=1, done.
Handles all cases efficiently.

Complexity

Time Complexity : O(n). Single pass.
Space Complexity : O(1). Only two variables.

Why It’s the Best

Linear time, optimal for large inputs.
Simple and elegant implementation.
Classic algorithm, interview favorite.

Comparison of Approaches

Approach	Time Complexity	Space Complexity	Best Use Case
Brute Force	O(n²)	O(1)	Small arrays, learning
Divide and Conquer	O(n log n)	O(log n)	Theoretical understanding
Kadane’s Algorithm	O(n)	O(1)	Best for efficiency, interviews

Edge Cases to Consider

Single element : [1] → 1; [-2] → -2.
All negative : [-1,-2,-3] → -1.
All positive : [1,2,3] → 6.
Mixed : [0,-1,2] → 2.

Final Thoughts

Brute Force : Correct but impractical.
Divide and Conquer : Interesting but overkill.
Kadane’s Algorithm : The best approach —fast, simple, and optimal. Master Kadane’s Algorithm for its elegance and interview relevance. Try finding the subarray itself as a follow-up challenge!