Maximum Subarray

ARRAYS & HASHING · MEDIUM

Builds on Day 6: Hash Maps & Sets

This problem doesn’t use a hash map itself, but it lives in the same “scan an array once, keep a running summary instead of re-deriving it” family of ideas — read that lesson first if tracking running state across a single pass still feels unfamiliar.

The problem

You’re given an array of integers nums — it may contain negative numbers. Find the contiguous subarray (a run of consecutive elements, no skipping around) that has the largest possible sum, and return that sum — not the subarray itself. The subarray must contain at least one number; you can’t “opt out” and claim an empty subarray sums to zero.

Example: nums = [-2,1,-3,4,-1,2,1,-5,4] → 6, from the subarray [4,-1,2,1]. A single-element array like [1] just returns 1. And because “at least one number” is a hard requirement, an all-negative array like [-3,-1,-8,-2] returns -1 — the least-negative single element — never 0.

Solution 1: Brute force — every window, with a running sum

The most direct reading of the problem is “try every contiguous window and keep the best sum.” For each start, walk end forward and maintain a running sum, adding just nums[end] each step instead of re-summing the whole window each time. That’s O(n²) total.

function maxSubArrayBrute(nums) {
  let best = -Infinity;
  for (let start = 0; start < nums.length; start++) {
    let sum = 0;
    for (let end = start; end < nums.length; end++) {
      sum += nums[end];
      best = Math.max(best, sum);
    }
  }
  return best;
}

Complexity: O(n²) time, O(1) space.

Solution 2: Kadane’s algorithm — extend or restart

At each index, you only ever need to answer one question: is it better to extend the current run, or restart fresh at this element? Extending is only worth it if the run-so-far is still positive; the moment it drags you down, cut your losses and restart at the current element. Track the best sum seen across every restart.

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] — best subarray is [4, -1, 2, 1], sum 6

Press play to run Kadane's single pass.

current sum: — · best sum: —

Step 0 / 9

▶ Play — O(n)↺ Reset

function maxSubArray(nums) {
  let cur = nums[0];
  let best = nums[0];
  for (let i = 1; i < nums.length; i++) {
    cur = Math.max(nums[i], cur + nums[i]);
    best = Math.max(best, cur);
  }
  return best;
}

Complexity: O(n) time, O(1) space — one pass, no nested loop.

Complexity comparison

Solution	Time	Space
Brute force (running sum)	O(n²)	O(1)
Kadane’s algorithm	O(n)	O(1)

Same space cost either way — the win here is purely in cutting the nested loop down to a single pass.

Interview corner

Q: Why is it safe for currentSum to summarize the entire scan so far, without keeping any other history?

• currentSum is defined as “the best sum of a subarray ending exactly at the current index” — that’s a complete answer for this index, not a partial one.
• Any subarray ending at index i is either the single element nums[i], or some earlier subarray extended by nums[i] — and the best “earlier subarray” for that purpose is exactly the best one ending at i-1, which is what the previous currentSum already holds.
• Nothing further back than i-1 can ever matter once currentSum at i-1 is known — that’s what makes O(1) extra state enough.

Q: Why must maxSum be initialized to nums[0], and not 0?

• The problem requires the subarray to contain at least one number — an empty subarray (implicitly summing to 0) is not a valid answer.
• Initializing to 0 would silently let that invalid empty subarray win whenever every real subarray sums to something negative — exactly the all-negative-array case, e.g. [-3,-1,-8,-2], whose correct answer is -1, not 0.
• Seeding both currentSum and maxSum with the first real element instead sidesteps the whole “what does empty even mean here” question.

Q: This solution only returns the maximum sum — how would you adapt it to also return the winning subarray itself?

• Track one more index alongside currentSum: runStart, the index where the current run began. Reset it to i whenever the algorithm restarts instead of extends.
• Whenever maxSum updates, also snapshot bestStart = runStart and bestEnd = i — exactly what the visualizations above are doing under the hood to know which window to highlight as “sorted” at the end.
• This adds O(1) extra bookkeeping — no change to the O(n) time or O(1) space bounds.

Q: Trick question — what does this log?

const nums = [];
console.log(Math.max(...nums));

• Answer: -Infinity — not undefined, and not a thrown error.
• Math.max() called with zero arguments (which is exactly what Math.max(...[]) spreads down to) is specified to return -Infinity — the identity value for “the maximum of nothing.”
• Both solutions on this page use Math.max heavily, but never on a possibly-empty spread — that’s exactly why the “at least one number” guarantee in the problem statement matters in practice.
• ⚠ Trap: if you were tempted to “one-line” a solution as something like Math.max(...allWindowSums), an accidentally-empty nums wouldn’t throw or warn you — it would silently return -Infinity, a wrong-looking number that’s easy to miss in review precisely because nothing crashes.

Quiz

Quiz: 1. What’s the key recurrence at the heart of Kadane’s algorithm?

currentSum = Math.max(nums[i], currentSum + nums[i]) — either extend the previous run or start fresh at this element

currentSum = Math.max(nums[i], currentSum + nums[i]) is the entire recurrence: either extend the previous run by adding this element, or abandon it and start fresh at this element alone, whichever gives the bigger sum.

Quiz: 2. Why does this page compare Kadane’s algorithm against the O(n²) running-sum brute force, rather than the fully naive O(n³) version?

The O(n³) version’s extra cost comes from redundant re-summation, not the core algorithmic idea — the running-sum O(n²) version gives a cleaner, more meaningful complexity comparison

The fully naive O(n³) version’s slowness comes from redundant re-summation, an inefficiency unrelated to the actual algorithmic idea being compared. The running-sum O(n²) version keeps the same “try every window” shape but removes that redundancy, giving a genuine two-step complexity story (O(n²) to O(n)) against Kadane’s algorithm.

Quiz: 3. For the all-negative input [-3,-1,-8,-2], what should the function return?

-1 — the least-negative single element, since the subarray must contain at least one number

The problem requires the subarray to contain at least one number, so an empty (implicitly zero-sum) subarray is never a valid answer. For an all-negative array, the best you can do is the single least-negative element.

Quiz: 4. What specifically causes the drop from O(n²) to O(n) between the two solutions?

Kadane’s replaces checking every (start, end) window with two running variables updated once per index in a single pass

The brute force examines O(n²) distinct (start, end) windows, one at a time. Kadane’s algorithm replaces all of that with two running variables — currentSum and maxSum — updated once per index in a single O(n) pass, which is what drops the time bound from quadratic to linear.

Quiz: 5. Why must maxSum = Math.max(maxSum, currentSum) run on every loop iteration, not just when the run restarts?

The winning subarray can end at any index, including one where the run kept extending rather than restarting — skipping those iterations could miss it

The best subarray doesn’t have to end at the very last index scanned — it could end anywhere. If maxSum only updated when a restart happened, a run that kept extending and growing larger without ever restarting could be missed entirely.