BudiBadu Logo

Maximum Subarray Sum

Array Medium 15 views
Like14

Maximum Subarray Sum asks for the largest possible sum of any contiguous segment in an integer array. The segment must be contiguous, but its length can vary from one element up to the full array. For arrays that contain both gains and losses, the goal is to isolate the strongest continuous run. In this dataset, empty input is treated as a special case that returns zero.

The standard solution is Kadane?s algorithm. Scan once while tracking two values: the best sum ending at the current index, and the best global sum seen so far. At each step, decide whether to extend the previous segment or start fresh from the current value. This local decision rule gives linear complexity and avoids expensive nested loops over all start-end combinations.

Judge behavior includes mixed positive/negative arrays, single-element arrays, all-negative arrays, and empty arrays. Return one integer maximum sum only. Accuracy depends on correctly handling reset logic when running sums become harmful and preserving the best answer even when late values drop sharply. This problem is foundational for interval optimization patterns where contiguous constraints matter more than total count of selected elements.

One subtle edge case is all-negative input: the correct answer is the largest single value, not zero, unless the input itself is empty in this challenge. So initialize tracking from actual data when available, and use explicit empty-array handling to satisfy both behavior branches cleanly.

Examples

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 - Budibadu
Recommendation Algorithm Flow for Maximum Subarray Sum - Budibadu

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;
    }
}