Maximum Subarray

Examples

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

The subarray [4, -1, 2, 1] adds up to 6, which is the largest sum of any contiguous stretch.

Input: nums = [1]
Output: 1

The only subarray is [1] itself.

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

The whole array sums to 23, and no smaller stretch beats that.

Constraints

• 1 <= nums.length <= 10^5

• -10^4 <= nums[i] <= 10^4

Approach

Checking every possible subarray works but repeats a huge amount of summing. The key insight is about the running sum as you scan left to right: if the sum of the subarray ending at the previous position is negative, it can only hurt any subarray that continues past it - so the greedy choice is to throw that prefix away and start fresh from the current number.

This is Kadane's algorithm: walk through the array once, keeping a running sum that resets to the current element whenever it would otherwise drop below the current element's own value, and track the best running sum seen at any point.

Solutions

Brute Force - Check Every Subarray

For every starting index, extend the subarray one element at a time and track the running sum, comparing against the best seen so far.

function maxSubArray(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;
}

Time: O(n^2) · Space: O(1)

Optimal - Kadane's Algorithm

Keep a running sum that represents the best subarray ending at the current position. Whenever that running sum turns negative, reset it to 0 (drop the prefix), since a negative prefix can never help a future sum.

function maxSubArray(nums) {
  let best = nums[0];
  let curr = 0;
  for (const num of nums) {
    if (curr < 0) curr = 0;
    curr += num;
    best = Math.max(best, curr);
  }
  return best;
}

Time: O(n) · Space: O(1)