3.9 Maximum Subarray

3.9.1 Problem Metadata

3.9.2 Description

Given an integer array nums, find the contiguous subarray with the largest sum and return that sum.

3.9.3 Examples

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

3.9.4 Constraints

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

3.9.5 Solution - Kadane’s Algorithm

3.9.5.1 Walkthrough

This solution uses Kadane’s Algorithm (see Kadane’s Algorithm), a classic dynamic programming technique for finding the maximum sum of a contiguous subarray.

Core Strategy:

The key insight is to maintain a running state representing the best subarray ending at the current position. At each element, we make a critical decision:

  1. Start fresh from the current element (begin a new subarray)
  2. Extend the previous subarray by including the current element

This decision is captured by the recurrence relation:

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

where current represents the maximum sum of a subarray ending at index i.

Why max(nums[i], current + nums[i])?

  • nums[i]: Start a new subarray from this element
  • current + nums[i]: Extend the previous best subarray

If the previous sum (current) is negative, adding it to nums[i] would only decrease the value. Starting fresh from nums[i] gives a better result.

Step-by-step execution:

For the array [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

i=0: nums[0]=-2
  current = -2 (first element)
  maxSum = -2

i=1: nums[1]=1
  current = max(1, -2+1) = max(1, -1) = 1 (start fresh!)
  maxSum = max(-2, 1) = 1

i=2: nums[2]=-3
  current = max(-3, 1+(-3)) = max(-3, -2) = -2 (extend)
  maxSum = max(1, -2) = 1

i=3: nums[3]=4
  current = max(4, -2+4) = max(4, 2) = 4 (start fresh!)
  maxSum = max(1, 4) = 4

i=4: nums[4]=-1
  current = max(-1, 4+(-1)) = max(-1, 3) = 3 (extend)
  maxSum = max(4, 3) = 4

i=5: nums[5]=2
  current = max(2, 3+2) = max(2, 5) = 5 (extend)
  maxSum = max(4, 5) = 5

i=6: nums[6]=1
  current = max(1, 5+1) = max(1, 6) = 6 (extend)
  maxSum = max(5, 6) = 6

i=7: nums[7]=-5
  current = max(-5, 6+(-5)) = max(-5, 1) = 1 (extend)
  maxSum = max(6, 1) = 6

i=8: nums[8]=4
  current = max(4, 1+4) = max(4, 5) = 5 (extend)
  maxSum = max(6, 5) = 6

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

Key Insight: At each position, we only need to know the best subarray ending at the previous position. We don’t need to track all possible subarrays, making this approach highly efficient.

3.9.5.2 Analysis

  • Time Complexity: O(n)
    • Single pass through the array
    • Each element is visited exactly once
    • Each iteration performs constant-time operations (two comparisons and assignments)
    • No nested loops or recursion
    • This is optimal since we must examine every element at least once
  • Space Complexity: O(1)
    • Only uses two variables (current and maxSum) regardless of input size
    • No additional data structures needed
    • No recursion stack space
    • This is optimal for the iterative approach

Why This Approach is Optimal:

  • We cannot do better than O(n) time since we must examine every element
  • We cannot use less than O(1) space while maintaining necessary state
  • Kadane’s algorithm achieves both optimal time and space complexity

3.9.5.3 Implementation Steps

Initialization:

  1. Initialize current = nums[0] (maximum sum of subarray ending at position 0)
  2. Initialize maxSum = nums[0] (global maximum sum found so far)

Main Loop (iterate from index 1 to n-1):

For each element nums[i]:

  1. Update current (best subarray ending at position i):
    • Compare two choices:
      • Start fresh: nums[i] (begin new subarray from current element)
      • Extend: current + nums[i] (add current element to previous subarray)
    • Set current = Math.max(nums[i], current + nums[i])
    • Critical insight: If current was negative, starting fresh is always better
  2. Update global maximum:
    • Set maxSum = Math.max(maxSum, current)
    • Track the best result seen across all positions

Return:

  1. Return maxSum (the maximum subarray sum)

3.9.5.4 Code - Java

public int maxSubArray(int[] nums) {
    int current = nums[0];
    int maxSum = nums[0];

    for (int i = 1; i < nums.length; i++) {
        current = Math.max(nums[i], current + nums[i]);
        maxSum = Math.max(maxSum, current);
    }

    return maxSum;
}

3.9.5.5 Code - Golang

func maxSubArray(nums []int) int {
    current := nums[0]
    maxSum := nums[0]

    for i := 1; i < len(nums); i++ {
        num := nums[i];
        current = max(num, current + num)        
        maxSum = max(maxSum, current)
    }

    return maxSum
}