Maximum Subarray

LeetCode 53 | Difficulty: Medium

Problem Description

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.

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

Approach

This problem is a classic application of Kadane's Algorithm, which uses dynamic programming principles:

1. Key Insight: At each position i, we decide whether to:

   • Extend the previous subarray by adding nums[i]
   • Start a new subarray from nums[i]

2. Decision Rule: If current_sum + nums[i] < nums[i], it's better to start fresh from nums[i]

3. Track the Maximum: While iterating, we keep track of the best sum seen so far

Walkthrough for Example 1:

Index	nums[i]	sum (running)	best (max so far)	Action
0	-2	-2	-2	Start
1	1	1	1	Restart (1 > -2+1)
2	-3	-2	1	Extend
3	4	4	4	Restart (4 > -2+4)
4	-1	3	4	Extend
5	2	5	5	Extend
6	1	6	6	Extend
7	-5	1	6	Extend
8	4	5	6	Extend

Complexity Analysis

• Time Complexity: $O(N)$ — Single pass through the array
• Space Complexity: $O(1)$ — Only using a few variables

Solution

public int MaxSubArray(int[] nums)
{
    int sum = nums[0], best = nums[0];
    int start = 0, end = 0, beg = 0;
    
    for (int i = 1; i < nums.Length; i++)
    {
        sum = sum + nums[i];
        
        // If starting fresh is better, reset the beginning
        if (sum <= nums[i])
        {
            sum = nums[i];
            beg = i;
        }
        
        // Track the best sum and its indices
        if (best < sum)
        {
            best = sum;
            start = beg;
            end = i;
        }
    }
    
    return best;
}

Interview Tips

• Follow-up: Return indices — The solution above tracks start and end indices for the maximum subarray
• Follow-up: Divide and Conquer — Can be solved in $O(N \log N)$ by finding max in left half, right half, and crossing the middle
• Edge Cases:
  • All negative numbers → return the largest (least negative) element
  • Single element → return that element
  • All positive numbers → return sum of entire array

Related Problems

• 152. Maximum Product Subarray — Similar approach but with products (handle negatives carefully)
• 918. Maximum Sum Circular Subarray — Kadane's with wraparound consideration
• 1749. Maximum Absolute Sum of Any Subarray — Track both max and min subarrays