Maximum Subarray Solutions & Complexity

1. Define the problem

Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum, and return that sum. Track one running sum ending at the current index. At each step, extend or restart it — extend by adding the current element, or restart fresh at the current element, whichever is bigger.

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁴ ≤ nums_i ≤ 10⁴

Example

Inputnums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Output6

Explanation The subarray [4, -1, 2, 1] has the largest sum: 6.

2. Know the words first

In plain terms

Contiguous subarray: A run of elements taken from the array back-to-back, with nothing skipped — for example, [4, -1, 2] is contiguous in [-2, 1, -3, 4, -1, 2, 1].

3. Visualize the solution

Extend or restart the running sum at every index

0-2

2-3

4-1

7-5

Statuscurrent: -2 · best: -2

Seed the running sum and best-so-far with the first element, -2. The frame marks the best subarray so far: just [-2].

What happens in this step

nums = [-2, 1, -3, 4, -1, 2, 1, -5]

nums[0] = -2
current = best = -2

Nothing to compare yet — seed both the running sum and the best-so-far with the first element. The best subarray so far is the single element at index 0.

Step 1 of 6

Steps to visualize

The row is the input array. The walkthrough uses a shorter array, [-2, 1, -3, 4, -1, 2, 1, -5], so every element fits on one line.
Seed the running sum and the best-so-far with the first element.
At each later index, compare extending the running sum against restarting at just this element.
Keep whichever is bigger as the new running sum, and update the best-so-far if it improved.
The frame marks the best subarray found so far. After the last index, its sum is the answer.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Extend or restart the running sum at every index

0-2

2-3

4-1

7-5

Statuscurrent: -2 · best: -2

Seed the running sum and best-so-far with the first element, -2. The frame marks the best subarray so far: just [-2].

What happens in this step

nums = [-2, 1, -3, 4, -1, 2, 1, -5]

nums[0] = -2
current = best = -2

Nothing to compare yet — seed both the running sum and the best-so-far with the first element. The best subarray so far is the single element at index 0.

Step 1 of 6

5. Solution

Solution

solution.tsTypeScript

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

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

  return best;
}

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

6. Test cases

Test cases

Input	Expected	Covers
`nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]`	`6`	example from the docstring
`nums = [-3, -1, -2]`	`-1`	every value negative — the answer must still be negative, never 0
`nums = [5]`	`5`	smallest valid input, a single positive element
`nums = [-7]`	`-7`	smallest valid input, a single negative element
`nums = [1, 2, 3, 4]`	`10`	every value positive — the whole array is the answer
`nums = [1, 2]`	`3`	boundary case, exactly two elements, both kept
`nums = [5, 4, -1, 7, 8]`	`23`	a single dip that is still worth carrying through
`nums = [0, -1, 2, -1]`	`2`	a zero value mixed with negatives

Maximum Subarray