LeetCode. 53. Maximum Subarray

On this page

[Link] https://leetcode.com/problems/maximum-subarray/

Approach

The input array is guaranteed to be non-empty. Scan it once while tracking the largest sum of a subarray that must end at the current index (ending) and the largest sum seen anywhere (best). At each element, either extend the previous subarray or start a new one at the current element:

ending = max(nums[i], ending + nums[i])

After updating ending, update best if the new ending sum is larger. Initializing both values to nums[0] ensures every candidate is a non-empty subarray. In particular, when all values are negative, the algorithm returns the largest (least negative) single-element subarray instead of incorrectly returning zero.

The invariant is that after processing index i, ending is the maximum sum of any non-empty subarray ending at i, and best is the maximum sum of any non-empty subarray in the processed prefix.

Time complexity is O(N) and extra space complexity is O(1).

Java

class Solution {
    public int maxSubArray(int[] nums) {
        int ending = nums[0];
        int best = nums[0];
        for (int i = 1; i < nums.length; i++) {
            ending = Math.max(nums[i], ending + nums[i]);
            best = Math.max(best, ending);
        }
        return best;
    }
}