#61

Maximum Subarray

medium

arraydivide-and-conquerdynamic-programming

Given an integer array nums, find the contiguous subarray (containing at least one number) with the largest sum, and return that sum.

A subarray is a contiguous, non-empty slice of the array.

Example

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

Output: 6

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

Constraints

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

Intuition

A first pass just tries every possible subarray — every start i paired with every end j — adding a running sum as j grows so each subarray doesn't need to be re-summed from scratch, and keeps the largest total seen.

function maxSubArray(nums) {
  let best = nums[0];
  // Try every possible starting index.
  for (let i = 0; i < nums.length; i++) {
    let sum = 0;
    // Extend the subarray one element at a time, keeping a running sum instead of re-adding from i.
    for (let j = i; j < nums.length; j++) {
      sum += nums[j];
      // This start-i, end-j subarray is a new candidate — keep it if it beats the best seen so far.
      if (sum > best) best = sum;
    }
  }
  return best;
}

Brute force — every (start, end) pair, with a running sum: O(n²).

This is O(n²) — far more work than necessary. Can we do better?

Think about a narrower question: what's the best subarray that ends exactly at index i? Once that's answered for index i, index i + 1's answer builds directly on it — either extend the winning run by tacking on nums[i + 1], or the running sum has gone so negative that it's dragging the total down, in which case it's better to drop it and start fresh at nums[i + 1] alone. The "best ending here" question, once solved for i, is never re-derived for i + 1 — it's just reused. That's the overlapping-subproblems signature dynamic programming exists for.

Formally, let dp[i] be the largest sum of any subarray ending at index i. Then dp[i] = nums[i] + max(0, dp[i - 1]) — extend the previous run if it's still pulling its weight, or drop it and start over, since a negative prefix can only ever hurt whatever sum follows it. The overall answer is the largest dp[i] across every index.

Since dp[i] only ever depends on dp[i - 1], there's no need to keep the whole table — the stored solution rolls a single variable cur forward instead (cur holds dp[i - 1] going into each step, and dp[i] coming out of it), alongside best, the running maximum across all of them. This routine is often taught as a standalone greedy trick ("Kadane's algorithm"), but it's really this one-dimensional DP recurrence collapsed to O(1) space.

Walking it through:

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

i↓

-61

-23

cur = best = nums[0] = 4

Seed both trackers with the first element — it's the only subarray candidate so far.

i↓

-61

-23

cur = max(-6, 4 + -6) = max(-6, -2) = -2

Extending narrowly beats starting over at -6, but the running sum has now gone negative — a warning sign for the next step.

-61

i↓

-23

cur = max(5, -2 + 5) = max(5, 3) = 5 → drop the negative prefix

A negative running sum only drags down whatever follows it, so it's better to abandon indices 0-1 and restart at nums[2]. best updates to 5.

-61

i↓

-23

cur = max(-2, 5 + -2) = max(-2, 3) = 3

The run survives a dip: even though nums[3] is negative on its own, the total is still worth carrying forward.

-61

-23

i↓

cur = max(3, 3 + 3) = max(3, 6) = 6 → best updates to 6

Extending keeps winning; the running sum climbs past the previous best, to 6.

-61

-23

i↓

cur = max(1, 6 + 1) = max(1, 7) = 7 → best updates to 7

Final step: best becomes 7, the sum of [5, -2, 3, 1] — indices 2 through 5.

Optimization

Kadane's algorithm

Scan left to right keeping the best subarray sum ending at the current index: either extend the previous running sum or start fresh at the current element, whichever is larger. The overall answer is the maximum running sum seen. Starting both trackers at nums[0] handles the all-negative case correctly.

O(n) time, O(1) space.

function maxSubArray(nums) {
  // best sum of a subarray ending exactly at the current index (dp[i]); the first element is the only candidate so far.
  let best = nums[0];
  let cur = nums[0];
  for (let i = 1; i < nums.length; i++) {
    // Either extend the previous run, or abandon it and start fresh here — whichever is larger.
    cur = Math.max(nums[i], cur + nums[i]);
    // Track the best run seen anywhere, not just the one ending at the current index.
    best = Math.max(best, cur);
  }
  return best;
}

Complexity analysis

Time complexity: O(n). Here's why:

The loop runs once for every index from 1 up to the end — n - 1 iterations after cur and best are seeded at nums[0].
Each iteration does O(1) work: two Math.max comparisons and two assignments.

So the whole scan is O(n) — down from the brute force's O(n²), since each index's best-sum-ending-here answer is computed once instead of re-summed from every possible starting point.

Space complexity: O(1). Here's why:

Only two rolling variables, cur and best, are kept — never a full dp array of size n.
There's no recursion, so no call stack to add on top.

Each dp[i] only ever depends on dp[i-1], so the table collapses to O(1) instead of the O(n) a naive array-backed fill would use.

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
nums = [7]	7	Single element — no choice but to take it, even with nothing to compare it against.
nums = [-8,-3,-6,-2,-5,-4]	-2	Every element negative — the best subarray is the least negative single element; the answer must not default to an empty subarray's sum of 0.
nums = [4,4,4,4]	16	All-equal positive values — extending never hurts, so the whole array is the best subarray.
nums = [-5,2,3,-1,4]	8	A negative first element drags down any subarray that includes it — the optimal run drops it and starts fresh at index 1: 2 + 3 - 1 + 4 = 8.
nums = [6,-2,6]	10	A dip in the middle is still worth crossing when the values on both sides outweigh it: 6 - 2 + 6 = 10.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor