Code Logo

Maximum Subarray Sum

Published at05 Jan 2026
Created by
Kadane Algorithm Medium 40 views
Like14

This problem asks for the largest sum you can get from one contiguous subarray. Contiguous means the numbers must stay next to each other in the original array, so you cannot skip a bad number in the middle and still call it one subarray.

As you scan from left to right, each position raises the same question: is it better to continue the subarray you already have, or throw it away and start fresh from the current number? That choice is the whole heart of the problem.

For example, in [-2,1,-3,4,-1,2,1,-5,4], the best subarray is [4,-1,2,1], which sums to 6. In [1], the answer is just 1. If every number is negative, like [-1,-2,-3], you still have to pick some contiguous subarray, so the answer is -1.

So the task is to find the highest possible sum of any one unbroken segment of the array and return that sum.

Example Input & Output

Example 1
Input
arr = [-1,-2,-3]
Output
-1
Explanation

Since all numbers are negative, the subarray [-1] is chosen as it has the largest sum among all possible subarrays.

Example 2
Input
arr = [1]
Output
1
Explanation

The array contains only one element, so the subarray [1] is the only possible subarray with a sum of 1.

Example 3
Input
arr = [-2,1,-3,4,-1,2,1,-5,4]
Output
6
Explanation

The subarray [4,-1,2,1] has the largest sum = 6, as it is the contiguous sequence with the highest total when summing its elements.

Algorithm Flow

Recommendation Algorithm Flow for Maximum Subarray Sum

Solution Approach

Find the maximum sum of a contiguous subarray using Kadane's algorithm. Maintain a running sum. If it becomes negative, reset it to 0 (starting a new subarray from the next element). Track the maximum running sum seen.

function maxSubArray(nums) {
  var maxSum = nums[0], curSum = 0;
  for (var i = 0; i < nums.length; i++) {
    curSum += nums[i];
    if (curSum > maxSum) maxSum = curSum;
    if (curSum < 0) curSum = 0;
  }
  return maxSum;
}

Resetting negative running sums effectively discards prefixes that would reduce any future subarray sum. The maxSum variable captures the global maximum.

Time complexity is O(n), space complexity is O(1).

Best Answers

java
class Solution {
    public int max_subarray_sum(int[] nums) {
        if (nums.length == 0) return 0;
        int maxSoFar = nums[0];
        int currentMax = nums[0];
        for (int i = 1; i < nums.length; i++) {
            currentMax = Math.max(nums[i], currentMax + nums[i]);
            maxSoFar = Math.max(maxSoFar, currentMax);
        }
        return maxSoFar;
    }
}