Maximum Subarray

Find the contiguous subarray with the largest sum. Walk once, keeping the best sum of a subarray ending here: either extend the previous one or start fresh at the current number, whichever is bigger.

Traced input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] → 6. Original problem: neetcode.io/problems/maximum-subarray

Complexity

One pass, two variables.

Key idea

• cur = max(x, cur + x): a negative running sum only drags future sums down, so drop it.
• Track the best cur ever seen.
• Initialise with the first element so all-negative arrays work.

Common mistakes

• Initialising best to 0 returns 0 for all-negative input.
• Resetting cur to 0 instead of to x.

Solution

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

def maxSubArray(nums: List[int]) -> int:
    cur = best = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best

int maxSubArray(vector<int>& nums) {
    int cur = nums[0], best = nums[0];
    for (size_t i = 1; i < nums.size(); i++) {
        cur = max(nums[i], cur + nums[i]);
        best = max(best, cur);
    }
    return best;
}

Edge cases

Each one has its own trace in the interactive view.