Skip to main content

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