Maximum Subarray Sum (Kadane's Algorithm)

Problem Statement

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Constraints:

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

Examples:

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [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: [5,4,-1,7,8] has the largest sum = 23.

Approach 1: Kadane's Algorithm (Optimal)

Algorithm:

1. Initialize max_so_far and max_ending_here to the first element
2. For each element, decide whether to start a new subarray or extend the current one
3. Update max_so_far with the maximum sum found so far

Time Complexity: O(n)
Space Complexity: O(1)

Python:

def maxSubArray(nums):
    """
    Find maximum subarray sum using Kadane's algorithm
    Time: O(n)
    Space: O(1)
    """
    if not nums:
        return 0
    
    max_so_far = nums[0]
    max_ending_here = nums[0]
    
    for i in range(1, len(nums)):
        # Either extend the existing subarray or start a new one
        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

Java:

class Solution {
    /**
     * Find maximum subarray sum using Kadane's algorithm
     * Time: O(n)
     * Space: O(1)
     */
    public int maxSubArray(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        
        int maxSoFar = nums[0];
        int maxEndingHere = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            // Either extend the existing subarray or start a new one
            maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }
        
        return maxSoFar;
    }
}

Go:

// maxSubArray - Find maximum subarray sum using Kadane's algorithm
// Time: O(n)
// Space: O(1)
func maxSubArray(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    
    maxSoFar := nums[0]
    maxEndingHere := nums[0]
    
    for i := 1; i < len(nums); i++ {
        // Either extend the existing subarray or start a new one
        if maxEndingHere+nums[i] > nums[i] {
            maxEndingHere += nums[i]
        } else {
            maxEndingHere = nums[i]
        }
        
        if maxEndingHere > maxSoFar {
            maxSoFar = maxEndingHere
        }
    }
    
    return maxSoFar
}

JavaScript:

/**
 * Find maximum subarray sum using Kadane's algorithm
 * Time: O(n)
 * Space: O(1)
 */
function maxSubArray(nums) {
    if (nums.length === 0) {
        return 0;
    }
    
    let maxSoFar = nums[0];
    let maxEndingHere = nums[0];
    
    for (let i = 1; i < nums.length; i++) {
        // Either extend the existing subarray or start a new one
        maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }
    
    return maxSoFar;
}

C#:

public class Solution {
    /// <summary>
    /// Find maximum subarray sum using Kadane's algorithm
    /// Time: O(n)
    /// Space: O(1)
    /// </summary>
    public int MaxSubArray(int[] nums) {
        if (nums.Length == 0) {
            return 0;
        }
        
        int maxSoFar = nums[0];
        int maxEndingHere = nums[0];
        
        for (int i = 1; i < nums.Length; i++) {
            // Either extend the existing subarray or start a new one
            maxEndingHere = Math.Max(nums[i], maxEndingHere + nums[i]);
            maxSoFar = Math.Max(maxSoFar, maxEndingHere);
        }
        
        return maxSoFar;
    }
}

Approach 2: Divide and Conquer

Algorithm:

1. Divide the array into two halves
2. Find maximum subarray in left half, right half, and crossing the middle
3. Return the maximum of the three

Time Complexity: O(n log n)
Space Complexity: O(log n)

Python:

def maxSubArray(nums):
    """
    Find maximum subarray sum using divide and conquer
    Time: O(n log n)
    Space: O(log n)
    """
    def maxCrossingSum(arr, left, mid, right):
        # Find maximum sum in left half
        left_sum = float('-inf')
        total = 0
        for i in range(mid, left - 1, -1):
            total += arr[i]
            if total > left_sum:
                left_sum = total
        
        # Find maximum sum in right half
        right_sum = float('-inf')
        total = 0
        for i in range(mid + 1, right + 1):
            total += arr[i]
            if total > right_sum:
                right_sum = total
        
        return left_sum + right_sum
    
    def maxSubArraySum(arr, left, right):
        if left == right:
            return arr[left]
        
        mid = (left + right) // 2
        
        return max(
            maxSubArraySum(arr, left, mid),
            maxSubArraySum(arr, mid + 1, right),
            maxCrossingSum(arr, left, mid, right)
        )
    
    return maxSubArraySum(nums, 0, len(nums) - 1)

Java:

class Solution {
    /**
     * Find maximum subarray sum using divide and conquer
     * Time: O(n log n)
     * Space: O(log n)
     */
    public int maxSubArray(int[] nums) {
        return maxSubArraySum(nums, 0, nums.length - 1);
    }
    
    private int maxSubArraySum(int[] arr, int left, int right) {
        if (left == right) {
            return arr[left];
        }
        
        int mid = (left + right) / 2;
        
        return Math.max(
            Math.max(maxSubArraySum(arr, left, mid),
                    maxSubArraySum(arr, mid + 1, right)),
            maxCrossingSum(arr, left, mid, right)
        );
    }
    
    private int maxCrossingSum(int[] arr, int left, int mid, int right) {
        // Find maximum sum in left half
        int leftSum = Integer.MIN_VALUE;
        int total = 0;
        for (int i = mid; i >= left; i--) {
            total += arr[i];
            if (total > leftSum) {
                leftSum = total;
            }
        }
        
        // Find maximum sum in right half
        int rightSum = Integer.MIN_VALUE;
        total = 0;
        for (int i = mid + 1; i <= right; i++) {
            total += arr[i];
            if (total > rightSum) {
                rightSum = total;
            }
        }
        
        return leftSum + rightSum;
    }
}

Go:

// maxSubArray - Find maximum subarray sum using divide and conquer
// Time: O(n log n)
// Space: O(log n)
func maxSubArray(nums []int) int {
    return maxSubArraySum(nums, 0, len(nums)-1)
}

func maxSubArraySum(arr []int, left, right int) int {
    if left == right {
        return arr[left]
    }
    
    mid := (left + right) / 2
    
    leftMax := maxSubArraySum(arr, left, mid)
    rightMax := maxSubArraySum(arr, mid+1, right)
    crossMax := maxCrossingSum(arr, left, mid, right)
    
    return max(leftMax, max(rightMax, crossMax))
}

func maxCrossingSum(arr []int, left, mid, right int) int {
    // Find maximum sum in left half
    leftSum := math.MinInt32
    total := 0
    for i := mid; i >= left; i-- {
        total += arr[i]
        if total > leftSum {
            leftSum = total
        }
    }
    
    // Find maximum sum in right half
    rightSum := math.MinInt32
    total = 0
    for i := mid + 1; i <= right; i++ {
        total += arr[i]
        if total > rightSum {
            rightSum = total
        }
    }
    
    return leftSum + rightSum
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

JavaScript:

/**
 * Find maximum subarray sum using divide and conquer
 * Time: O(n log n)
 * Space: O(log n)
 */
function maxSubArray(nums) {
    return maxSubArraySum(nums, 0, nums.length - 1);
}

function maxSubArraySum(arr, left, right) {
    if (left === right) {
        return arr[left];
    }
    
    const mid = Math.floor((left + right) / 2);
    
    const leftMax = maxSubArraySum(arr, left, mid);
    const rightMax = maxSubArraySum(arr, mid + 1, right);
    const crossMax = maxCrossingSum(arr, left, mid, right);
    
    return Math.max(leftMax, rightMax, crossMax);
}

function maxCrossingSum(arr, left, mid, right) {
    // Find maximum sum in left half
    let leftSum = -Infinity;
    let total = 0;
    for (let i = mid; i >= left; i--) {
        total += arr[i];
        if (total > leftSum) {
            leftSum = total;
        }
    }
    
    // Find maximum sum in right half
    let rightSum = -Infinity;
    total = 0;
    for (let i = mid + 1; i <= right; i++) {
        total += arr[i];
        if (total > rightSum) {
            rightSum = total;
        }
    }
    
    return leftSum + rightSum;
}

C#:

public class Solution {
    /// <summary>
    /// Find maximum subarray sum using divide and conquer
    /// Time: O(n log n)
    /// Space: O(log n)
    /// </summary>
    public int MaxSubArray(int[] nums) {
        return MaxSubArraySum(nums, 0, nums.Length - 1);
    }
    
    private int MaxSubArraySum(int[] arr, int left, int right) {
        if (left == right) {
            return arr[left];
        }
        
        int mid = (left + right) / 2;
        
        int leftMax = MaxSubArraySum(arr, left, mid);
        int rightMax = MaxSubArraySum(arr, mid + 1, right);
        int crossMax = MaxCrossingSum(arr, left, mid, right);
        
        return Math.Max(leftMax, Math.Max(rightMax, crossMax));
    }
    
    private int MaxCrossingSum(int[] arr, int left, int mid, int right) {
        // Find maximum sum in left half
        int leftSum = int.MinValue;
        int total = 0;
        for (int i = mid; i >= left; i--) {
            total += arr[i];
            if (total > leftSum) {
                leftSum = total;
            }
        }
        
        // Find maximum sum in right half
        int rightSum = int.MinValue;
        total = 0;
        for (int i = mid + 1; i <= right; i++) {
            total += arr[i];
            if (total > rightSum) {
                rightSum = total;
            }
        }
        
        return leftSum + rightSum;
    }
}

Approach 3: Brute Force

Algorithm:

1. Generate all possible subarrays
2. Calculate sum for each subarray
3. Return the maximum sum found

Time Complexity: O(n²)
Space Complexity: O(1)

Python:

def maxSubArray(nums):
    """
    Find maximum subarray sum using brute force
    Time: O(n²)
    Space: O(1)
    """
    if not nums:
        return 0
    
    max_sum = float('-inf')
    
    for i in range(len(nums)):
        current_sum = 0
        for j in range(i, len(nums)):
            current_sum += nums[j]
            max_sum = max(max_sum, current_sum)
    
    return max_sum

Java:

class Solution {
    /**
     * Find maximum subarray sum using brute force
     * Time: O(n²)
     * Space: O(1)
     */
    public int maxSubArray(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        
        int maxSum = Integer.MIN_VALUE;
        
        for (int i = 0; i < nums.length; i++) {
            int currentSum = 0;
            for (int j = i; j < nums.length; j++) {
                currentSum += nums[j];
                maxSum = Math.max(maxSum, currentSum);
            }
        }
        
        return maxSum;
    }
}

Go:

// maxSubArray - Find maximum subarray sum using brute force
// Time: O(n²)
// Space: O(1)
func maxSubArray(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    
    maxSum := math.MinInt32
    
    for i := 0; i < len(nums); i++ {
        currentSum := 0
        for j := i; j < len(nums); j++ {
            currentSum += nums[j]
            if currentSum > maxSum {
                maxSum = currentSum
            }
        }
    }
    
    return maxSum
}

JavaScript:

/**
 * Find maximum subarray sum using brute force
 * Time: O(n²)
 * Space: O(1)
 */
function maxSubArray(nums) {
    if (nums.length === 0) {
        return 0;
    }
    
    let maxSum = -Infinity;
    
    for (let i = 0; i < nums.length; i++) {
        let currentSum = 0;
        for (let j = i; j < nums.length; j++) {
            currentSum += nums[j];
            maxSum = Math.max(maxSum, currentSum);
        }
    }
    
    return maxSum;
}

C#:

public class Solution {
    /// <summary>
    /// Find maximum subarray sum using brute force
    /// Time: O(n²)
    /// Space: O(1)
    /// </summary>
    public int MaxSubArray(int[] nums) {
        if (nums.Length == 0) {
            return 0;
        }
        
        int maxSum = int.MinValue;
        
        for (int i = 0; i < nums.Length; i++) {
            int currentSum = 0;
            for (int j = i; j < nums.Length; j++) {
                currentSum += nums[j];
                maxSum = Math.Max(maxSum, currentSum);
            }
        }
        
        return maxSum;
    }
}

Key Insights

1. Kadane's Algorithm: The optimal solution that makes a key insight - if the current subarray sum becomes negative, we should start a new subarray.
2. Dynamic Programming: Kadane's algorithm is essentially a DP approach where we decide at each element whether to extend the current subarray or start a new one.
3. Divide and Conquer: More complex but demonstrates the power of recursive problem solving.
4. Greedy Choice: At each step, we make the locally optimal choice (extend or start new).

Edge Cases

• Single element array: [5] → result is 5
• All negative numbers: [-3,-2,-1] → result is -1 (the least negative)
• All positive numbers: [1,2,3] → result is 6 (sum of all)
• Mixed with zeros: [0,0,0] → result is 0

Test Cases

# Test case 1: Mixed positive and negative
assert maxSubArray([-2,1,-3,4,-1,2,1,-5,4]) == 6

# Test case 2: Single element
assert maxSubArray([1]) == 1

# Test case 3: All positive
assert maxSubArray([5,4,-1,7,8]) == 23

# Test case 4: All negative
assert maxSubArray([-3,-2,-1]) == -1

# Test case 5: Single negative
assert maxSubArray([-1]) == -1

Follow-up Questions

1. Find the actual subarray: Modify the algorithm to return the start and end indices of the maximum subarray.
2. Maximum subarray with at least k elements: Find the maximum sum subarray with at least k elements.
3. Maximum subarray with exactly k elements: Find the maximum sum subarray with exactly k elements.
4. Circular array: What if the array is circular (can wrap around)?

Common Mistakes

1. Not handling all negative arrays: Forgetting that the result can be a single negative number.
2. Off-by-one errors: Incorrectly initializing or updating the maximum values.
3. Not considering empty subarrays: The problem requires at least one element.
4. Integer overflow: Not handling very large numbers properly.

Trade-offs

• Kadane's vs Divide & Conquer: Kadane's is simpler and more efficient
• Brute Force: Easy to understand but inefficient for large inputs
• Space Complexity: All approaches use O(1) space except divide & conquer
• Time Complexity: Kadane's is optimal at O(n)