Maximum Subarray

Problem Description

Given an integer array nums, find the subarray with the largest sum, and return its sum.

A subarray is a contiguous non-empty sequence of elements within an array.

Examples

Constraints

• 1 ≤ nums.length ≤ 10⁵
• -10⁴ ≤ nums[i] ≤ 10⁴

Discarding Negative Prefixes

The naive approach is evaluating all O(n²) subarrays. This is too slow for arrays of size 10⁵.

To optimize, note that a prefix sum is only useful to subsequent elements if it is positive. If the sum of a prefix subarray is negative, adding it to any next element will only decrease the sum. We should discard that prefix entirely and reset our running sum to 0.

This is Kadane’s Algorithm:

• Iterate through the array, adding each number to a currSum.
• Update globalMax with the maximum of itself and currSum.
• If currSum becomes negative, reset currSum = 0 (discarding the negative prefix).

Solution 1: Kadane’s Algorithm (Optimal)

Scan the array once, tracking running sum and resetting to 0 when it drops below zero.

class Solution {
    public int maxSubArray(int[] nums) {
        int globalMax = nums[0];
        int currSum = 0;

        for (int num : nums) {
            currSum += num;
            globalMax = Math.max(globalMax, currSum);
            // if running sum is negative, discard prefix and start fresh
            if (currSum < 0) {
                currSum = 0;
            }
        }
        return globalMax;
    }
}

class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        global_max = nums[0]
        curr_sum = 0

        for num in nums:
            curr_sum += num
            global_max = max(global_max, curr_sum)
            # if running sum is negative, discard prefix and start fresh
            if curr_sum < 0:
                curr_sum = 0

        return global_max

#include <vector>
#include <algorithm>

class Solution {
public:
    int maxSubArray(std::vector<int>& nums) {
        int globalMax = nums[0];
        int currSum = 0;

        for (int num : nums) {
            currSum += num;
            globalMax = std::max(globalMax, currSum);
            // if running sum is negative, discard prefix and start fresh
            if (currSum < 0) {
                currSum = 0;
            }
        }
        return globalMax;
    }
};

Complexity Analysis:

• Time Complexity: O(n) where n is the length of array nums. We scan the array once.
• Space Complexity: O(1) auxiliary space as we only use two tracking variables.

Where it breaks: Nothing breaks for standard integer arrays. If the input contains only negative values (e.g. [-3, -2, -5]), the code correctly returns -2 because the globalMax is updated before resetting currSum to 0. The order of operations is vital.

Common Mistakes

• Resetting currSum to 0 before updating globalMax. If you do this on an array of all negative numbers, your algorithm will incorrectly return 0 because it discards the negative elements before logging them.
• Initializing globalMax = 0. If the array only contains negative values (e.g. [-3]), the correct answer is -3. Initializing to 0 returns an incorrect result. Initialize to nums[0].
• Forgetting that subarrays must be contiguous. Do not confuse this with subsequences, which allow skipping elements.

Frequently Asked Questions

Why does this greedy prefix reset work? Because a negative sum prefix can never contribute to a larger total sum for any subarray starting after it. Discarding it is always mathematically sound.

How do we return the actual subarray bounds? You can track start and end indices. Keep a temporary start index that updates to i + 1 whenever currSum resets to 0. When globalMax is updated, record the current start index and the current index i as the optimal bounds.

What does this problem test in interviews? It tests your ability to optimize nested loops to linear O(n) scans, and handle negative boundaries correctly.

← All Problems