Maximum Subarray

find the subarray with the largest sum, and return its sum.

Maximum Subarray

Problem

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

A subarray is a continuous, non-empty part of the array.

Examples

Example 1

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6

• The subarray [4,-1,2,1] has the largest sum, which is 6.

Example 2

Input: nums = [1]
Output: 1

• The only subarray is [1].

Example 3

Input: nums = [5,4,-1,7,8]
Output: 23

• The whole array has the largest sum, which is 23.

Constraints

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

Follow up: After the O(n) solution, try the divide and conquer approach.

Main Idea

At each index i, we ask one question: "Should I extend the previous subarray, or start a new one here?"

• Let current be the best sum of a subarray that ends at index i.
• If the previous sum current is negative, it only makes the new sum smaller. So we drop it and start fresh from nums[i].
• If the previous sum is positive (or zero), we keep it and add nums[i].

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

The answer is the biggest current seen at any index. This is called Kadane's algorithm.

Note: If all numbers are negative, the answer is the largest single number. So we must not start best at 0. We start it with nums[0].

Solution 1: Brute Force

We check every subarray. For each start i, we keep a running sum as j moves forward.

var maxSubArray = function (nums) {
    let best = -Infinity;

    for (let i = 0; i < nums.length; i++) {
        let sum = 0;

        for (let j = i; j < nums.length; j++) {
            sum += nums[j];
            best = Math.max(best, sum);
        }
    }

    return best;
};

Complexity

• Time Complexity: O(n²)
  • We check every start and end pair. With n = 10^5, this is too slow.
• Space Complexity: O(1)
  • We use only a few variables.

Solution 2: Kadane's Algorithm (Optimal)

var maxSubArray = function (nums) {
    let current = nums[0];
    let best = nums[0];

    for (let i = 1; i < nums.length; i++) {
        // extend the previous subarray, or start a new one
        current = Math.max(nums[i], current + nums[i]);

        // keep the biggest sum seen so far
        best = Math.max(best, current);
    }

    return best;
};

How the Code Works

• Step 1: current and best start with nums[0]. A subarray with one element has only that sum.
• Step 2: For each next number, we choose the bigger of two options:
  • nums[i]: start a new subarray here.
  • current + nums[i]: extend the old subarray.
• Step 3: best keeps the biggest current seen so far.
• Step 4: We return best.

Dry Run

Let us take nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4].

The answer is 6.

Complexity

• Time Complexity: O(n)
  • We go through the array once.
• Space Complexity: O(1)
  • We use only two variables.

Solution 3: Divide and Conquer (Follow Up)

We split the array in the middle. The best subarray must be in one of three places:

• Fully in the left half.
• Fully in the right half.
• Crossing the middle, so it uses elements from both halves.

We solve the left and right halves with recursion. For the crossing case:

• Start at the middle and go left, keeping the best sum. This is the best sum ending at mid.
• Start at mid + 1 and go right, keeping the best sum. This is the best sum starting at mid + 1.
• Add both. This is the best crossing sum.

The answer is the maximum of the three.

var maxSubArray = function (nums) {
    function solve(left, right) {
        // one element
        if (left === right) return nums[left];

        const mid = Math.floor((left + right) / 2);

        // best sum fully in each half
        const leftBest = solve(left, mid);
        const rightBest = solve(mid + 1, right);

        // best sum that crosses the middle
        let sum = 0;
        let leftCross = -Infinity;
        for (let i = mid; i >= left; i--) {
            sum += nums[i];
            leftCross = Math.max(leftCross, sum);
        }

        sum = 0;
        let rightCross = -Infinity;
        for (let i = mid + 1; i <= right; i++) {
            sum += nums[i];
            rightCross = Math.max(rightCross, sum);
        }

        const crossBest = leftCross + rightCross;

        return Math.max(leftBest, rightBest, crossBest);
    }

    return solve(0, nums.length - 1);
};

How the Code Works

• Base case: With one element, the best sum is that element.
• Split: mid cuts the range into [left, mid] and [mid + 1, right].
• Crossing sum: The crossing subarray must include both nums[mid] and nums[mid + 1]. So we find the best sum going left from mid, and the best sum going right from mid + 1, and add them.
• We start leftCross and rightCross at -Infinity, so negative numbers still work.

Dry Run

Let us take nums = [-2, 1, -3, 4].

• Split into [-2, 1] and [-3, 4].
• Left half: best is 1. Right half: best is 4.
• Crossing: going left from index 1, the sums are 1 and -1, so leftCross = 1. Going right from index 2, the sums are -3 and 1, so rightCross = 1. Crossing = 1 + 1 = 2.
• Answer = max(1, 4, 2) = 4.

Complexity

• Time Complexity: O(n log n)
  • Each level of recursion does O(n) work for the crossing sums.
  • There are log n levels.
• Space Complexity: O(log n)
  • The recursion stack goes as deep as log n.

Comparison

Summary

• At each index, choose: extend the previous subarray or start new. current = max(nums[i], current + nums[i]).
• Start best with nums[0], so arrays with all negative numbers work.
• Kadane's algorithm runs in O(n) time and uses O(1) space.
• Divide and conquer splits the array. The best subarray is in the left half, in the right half, or crosses the middle.
• Divide and conquer runs in O(n log n) time and uses O(log n) space. It is slower than Kadane's, but it is a good way to practice the idea.
• Compare with Maximum Product Subarray: sums need only one value, but products need both the max and the min, because negatives flip the sign.