Maximum Sum Subarray (Kadane's Algorithm)

Share

Find the contiguous subarray with the largest sum.

Example 1
Input: nums=[-2,1,-3,4,-1,2,1,-5,4] → Output: 6. Subarray [4,-1,2,1] has sum 6.
Example 2
Input: nums=[1] → Output: 1

Solution Approach

Kadane's algorithm: track current sum and global max.

  • Initialize curSum = nums[0], maxSum = nums[0]
  • For each next element: curSum = max(num, curSum+num)
  • Update maxSum = max(maxSum, curSum)
  • Return maxSum
Java
public int maxSubArray(int[] nums) {
    int curSum = nums[0], maxSum = nums[0];
    for (int i = 1; i < nums.length; i++) {
        curSum = Math.max(nums[i], curSum + nums[i]);
        maxSum = Math.max(maxSum, curSum);
    }
    return maxSum;
}
  • Time Complexity: O(n)
  • Space Complexity: O(1)