Max Subarray Sum [Kadanes]

53.Maximum Subarray

Array

Dynamic Programming

Greedy

Problem Statement:

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:

Input:

nums = [-2,1,-3,4,-1,2,1,-5,4]

→

Output:

6

The subarray [4,-1,2,1] has the largest sum 6.

Algorithm:

1. Use Kadane's Algorithm with a slight modification:
2. Track current maximum subarray sum (currMax) and overall maximum (max)
3. For each element, decide whether to:
   • Start new subarray from current element (nums[i])
   • Or extend previous subarray (currMax + nums[i])
4. Update overall maximum if current maximum is larger
5. Initial values must be nums[0] since we need at least one element

Complexity:

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

Java Solution:

public int maxSubArray(int[] nums) {
    int currMax = nums[0];  // Tracks current subarray sum
    int max = nums[0];      // Tracks overall maximum sum

    // Start from second element since we initialized with first
    for (int i = 1; i < nums.length; i++) {
        // Either start new subarray from current element
        // Or extend previous subarray by adding current element
        currMax = Math.max(nums[i], currMax + nums[i]);
        
        // Update overall maximum if needed
        max = Math.max(max, currMax);
    }

    return max;
}

Python Solution:

def maxSubArray(self, nums: List[int]) -> int:
    curr_max = max_sum = nums[0]
    
    for num in nums[1:]:
        # Start new subarray or extend current one
        curr_max = max(num, curr_max + num)
        # Update overall maximum
        max_sum = max(max_sum, curr_max)
    
    return max_sum

C++ Solution:

int maxSubArray(vector<int>& nums) {
    int curr_max = nums[0];
    int max_sum = nums[0];
    
    for (int i = 1; i < nums.size(); i++) {
        // Either start new from current or extend previous
        curr_max = max(nums[i], curr_max + nums[i]);
        // Update overall maximum if needed
        max_sum = max(max_sum, curr_max);
    }
    
    return max_sum;
}