Code Logo

Maximum Subarray Sum

Published at05 Jan 2026
Created by
Medium 17 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
Recommendation Algorithm Flow for Maximum Subarray Sum

Solution Approach

The standard solution here is Kadane's algorithm. The idea is to keep track of the best subarray sum that ends at the current position, and also the best subarray sum seen anywhere so far.

Suppose we are at arr[i]. There are only two sensible choices for a subarray ending here: either start fresh at arr[i], or extend the previous subarray by adding arr[i].

That gives this update:

current = Math.max(arr[i], current + arr[i]);

If the old running sum is hurting us, we drop it and start over from the current value.

At the same time, we update the overall best answer:

best = Math.max(best, current);

Putting it together:

let current = arr[0];
let best = arr[0];

for (let i = 1; i < arr.length; i++) {
  current = Math.max(arr[i], current + arr[i]);
  best = Math.max(best, current);
}

If the array is empty, this problem's tests expect 0. Otherwise, after the loop, best is the maximum subarray sum. This runs in O(n) time and uses O(1) extra space.

Best Answers

java
class Solution {
    public int max_subarray_sum(int[] nums) {
        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;
    }
}