Maximum Subarray

Medium

💭 Introduction

You’re given an array of integers (which can be positive, negative, or zero). Your task is to find the contiguous subarray with the largest sum.

A subarray is a continuous part of an array.

For example, in [1, 2, 3], the subarrays are: [1], [2], [3], [1,2], [2,3], and [1,2,3].

Your goal is to find which contiguous subarray has the maximum sum.

🧩 Problem Statement

LeetCode #53 — Maximum Subarray

Given an integer array nums, find the subarray with the largest sum, and return its sum. A subarray is a contiguous non-empty sequence of elements within an array.

🔍 Example 1: 

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 2: 

Input: nums = [1]
Output: 1

Explanation:

The subarray [1] has the largest sum = 1.

🔍 Example 3: 

Input: nums = [5,4,-1,7,8]
Output: 23

Explanation:

The subarray [5,4,-1,7,8] has the largest sum = 23.

🧠 Step 1: Brute Force Intuition

The most straightforward approach is to check every possible subarray:

def maxSubArray(nums):
    max_sum = float('-inf')
    n = len(nums)
    
    for i in range(n):
        for j in range(i, n):
            # Calculate sum of subarray from i to j
            current_sum = sum(nums[i:j+1])
            max_sum = max(max_sum, current_sum)
    
    return max_sum

This checks all possible subarrays and keeps track of the maximum sum.

⏱️ Time Complexity: $O(n^3)$ (or $O(n^2)$ if we optimize the sum calculation)

📦 Space Complexity: $O(1)$

Problem: This is too slow for large arrays!

🤔 Step 2: The Key Insight

Here’s the crucial observation:

At each position i, you have two choices:

  1. Extend the previous subarray by including nums[i]
  2. Start fresh from nums[i]

When should you start fresh? When the previous sum becomes negative!

Why? Because adding a negative sum to the current element will only make it smaller.

For example:

  • If previous sum = -5 and current element = 3
  • Extending: -5 + 3 = -2
  • Starting fresh: 3
  • Starting fresh is better!

This leads us to Kadane’s Algorithm.

🚀 Step 3: Kadane’s Algorithm (The Elegant Solution)

At each position, we decide:

current_sum = max(nums[i], current_sum + nums[i])

This means: “Should I start a new subarray here, or extend the previous one?”

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sum = nums[0]
        current_sum = nums[0]
        
        for i in range(1, len(nums)):
            # Either extend previous subarray or start new
            current_sum = max(nums[i], current_sum + nums[i])
            # Update global maximum
            max_sum = max(max_sum, current_sum)
        
        return max_sum

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

i nums[i] current_sum max_sum Decision
0 -2 -2 -2 Start
1 1 1 1 Start fresh (1 > -2+1)
2 -3 -2 1 Extend (1-3 = -2)
3 4 4 4 Start fresh (4 > -2+4)
4 -1 3 4 Extend (4-1 = 3)
5 2 5 5 Extend (3+2 = 5)
6 1 6 6 Extend (5+1 = 6)
7 -5 1 6 Extend (6-5 = 1)
8 4 5 6 Extend (1+4 = 5)

Final answer: 6 (subarray [4,-1,2,1])

⏱️ Time Complexity: $O(n)$ — Single pass through the array

📦 Space Complexity: $O(1)$ — Only two variables

🎯 Step 4: Understanding as Dynamic Programming

Kadane’s Algorithm is actually a DP solution! Let’s formalize it:

Define: dp[i] = maximum sum of subarray ending at index i

Recurrence relation:

dp[i] = max(nums[i], dp[i-1] + nums[i])

Base case:

dp[0] = nums[0]

Answer:

max(dp[0], dp[1], ..., dp[n-1])

Here’s the explicit DP version:

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0] * n
        dp[0] = nums[0]
        max_sum = dp[0]
        
        for i in range(1, n):
            dp[i] = max(nums[i], dp[i-1] + nums[i])
            max_sum = max(max_sum, dp[i])
        
        return max_sum

⏱️ Time: $O(n)$

📦 Space: $O(n)$

🧮 Step 5: Space Optimization

Notice that dp[i] only depends on dp[i-1]. We don’t need the entire array!

This is exactly what we did in Step 3 with current_sum:

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sum = current_sum = nums[0]
        
        for num in nums[1:]:
            current_sum = max(num, current_sum + num)
            max_sum = max(max_sum, current_sum)
        
        return max_sum

This is the optimal solution — Kadane’s Algorithm with O(1) space.

⏱️ Time Complexity: $O(n)$

📦 Space Complexity: $O(1)$

🔄 Step 6: Alternative Formulation

Some prefer this equivalent formulation:

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sum = float('-inf')
        current_sum = 0
        
        for num in nums:
            current_sum += num
            max_sum = max(max_sum, current_sum)
            
            # If current_sum becomes negative, reset to 0
            if current_sum < 0:
                current_sum = 0
        
        return max_sum

This version explicitly resets when the sum becomes negative, which is equivalent to starting fresh.

🎯 Key Insights

  1. Greedy + DP: Kadane’s Algorithm is both greedy (local decision) and DP (optimal substructure).

  2. The decision rule: At each position, decide whether to extend or start fresh based on whether the previous sum helps or hurts.

  3. Negative numbers: The algorithm handles negative numbers naturally — if all numbers are negative, it returns the least negative one.

  4. Optimal substructure: The maximum subarray ending at position i depends only on the maximum subarray ending at position i-1.

📊 Complexity Summary

Approach Time Space
Brute Force $O(n^3)$ or $O(n^2)$ $O(1)$
DP with Array $O(n)$ $O(n)$
Kadane’s Algorithm $O(n)$ $O(1)$

🌟 Follow-up: Finding the Actual Subarray

If you need to return the subarray itself (not just the sum):

class Solution:
    def maxSubArray(self, nums: List[int]) -> tuple:
        max_sum = current_sum = nums[0]
        start = end = 0
        temp_start = 0
        
        for i in range(1, len(nums)):
            if nums[i] > current_sum + nums[i]:
                current_sum = nums[i]
                temp_start = i
            else:
                current_sum = current_sum + nums[i]
            
            if current_sum > max_sum:
                max_sum = current_sum
                start = temp_start
                end = i
        
        return max_sum, nums[start:end+1]

💡 Related Problems

  • House Robber - Similar DP pattern
  • Maximum Product Subarray - Variant with multiplication
  • Best Time to Buy and Sell Stock - Similar greedy approach
  • Maximum Sum Circular Subarray - Circular array variant

🏆 Why This Problem Matters

  1. Interview favorite: One of the most common DP problems
  2. Pattern recognition: Teaches the “extend vs. start fresh” pattern
  3. Optimization: Shows how DP can be space-optimized
  4. Real-world applications: Stock trading, signal processing, data analysis