Maximum Subarray

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

A subarray is a slice of consecutive elements: you choose where it starts and ends, but you can't skip elements in the middle. Because the subarray must be non-empty, an all-negative array still has an answer — the single largest element.

For nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4], the slice [4, -1, 2, 1] adds up to 6, and no other contiguous stretch does better — so the answer is 6.

Hints

· Stuck? Reveal one nudge at a time.

The answer is a single sum, but the subarray must be contiguous — you can't cherry-pick elements. How expensive is it to check every possible contiguous stretch?

As you scan left to right, think about what a running total that has already dropped below zero can possibly do for the elements still ahead of it.

Keep one running sum: extend it while it helps, reset it to the current element the instant it turns negative, and track the best sum you've ever seen. That's Kadane's algorithm.

Common doubts

No — the problem requires a non-empty subarray. So even if every element is negative, you return the largest single element, not 0.

A negative running prefix can only lower the total of whatever follows it. Dropping it and restarting at the current element is never worse, and usually better.

Just the sum, as asked. To recover the actual slice, also track a start and end index whenever you update best or reset the run.

Interview follow-ups

· What an interviewer asks next.

Yes — split at the middle; the best subarray is in the left half, the right half, or crosses the boundary. Recurse on the halves and build the crossing sum by expanding outward from the midpoint, giving O(n log n).

That's 'Maximum Sum Circular Subarray': the answer is either a normal Kadane maximum, or total sum minus the minimum subarray (the wrap case) — with an all-negative array handled specially so you don't return an empty wrap.

Fun facts

Kadane's algorithm was devised by Jay Kadane in the 1980s — reportedly in under a minute after the problem was posed — a textbook example of collapsing dynamic programming into a single linear scan.
The 'reset a negative running total' trick reappears all over array DP: Maximum Product Subarray, Best Time to Buy and Sell Stock, and the circular-array variant are all descendants.

Asked at

AmazonMicrosoftGoogleBloombergAppleAdobe

Frequently Sometimes Occasionally

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 6.

Example 2

Input: nums = [1]
Output: 1
The subarray [1] has the largest sum 1.

Example 3

Input: nums = [5,4,-1,7,8]
Output: 23
The whole array [5,4,-1,7,8] has the largest sum 23.

Constraints

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

Maximum Subarray is where dynamic programming collapses into a single elegant scan. Kadane's algorithm is one of the most famous one-liners in all of DSA, and its core idea — a running total that has gone negative is dead weight, so drop it — reappears in Maximum Product Subarray, Best Time to Buy and Sell Stock, and the circular variant.

Prerequisites

Before you start

· Concepts used directly in the solution.

Contiguous subarray. A slice of consecutive elements — you pick start and end but can't skip the middle. That contiguity is what allows a running sum.

Running sum. A total you extend element by element, and the decision of when it's no longer worth carrying.

DP collapsed to a scan. The insight that "best subarray ending at i" depends only on the same answer at i-1, so one variable replaces a table.

Understand the problem

Given an array nums, find the contiguous, non-empty subarray with the largest sum and return that sum. Because it must be non-empty, an all-negative array still has an answer: its largest single element.

Worked example — nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

  current = best-sum ending here;  best = global best
  -2 → current −2, best −2
   1 → max(1, −2+1)=1,  best 1
  -3 → max(−3, 1−3)=−2, best 1
   4 → max(4, −2+4)=4,  best 4
  -1 → 3,  best 4
   2 → 5,  best 5
   1 → 6,  best 6   ✓  (subarray [4,-1,2,1])
  -5 → 1,  best 6
   4 → 5,  best 6

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Input validity

“Must the subarray be non-empty?”

Yes — so an all-negative array returns its largest element, not 0. This decides how you initialize best.

“Can values be negative?”

Yes — that's the whole difficulty. If everything were non-negative, the answer would just be the total sum.

Edge cases

“What if every element is negative?”

Return the single largest (least-negative) element — the non-empty rule forbids an empty subarray of sum 0.

“What about a single-element array?”

That element is the answer.

Output format

“Return the sum, or the subarray itself?”

Just the sum here. To recover the slice, also track start/end indices when you update best or reset the run.

Constraints & scale

“How large can the array be?”

Up to 10^5. An O(n²) sum-every-window approach is ~10^10 ops and will time out; Kadane is O(n).

The ideal opening — say it like this

A couple of questions.

The subarray must be non-empty, so an all-negative array returns its largest element?

I return the sum, not the subarray itself?

Given the size and negatives, I'll use Kadane's — O(n) time, O(1) space.

Key observations

1Aha

A negative running prefix can only hurt what follows

If the sum of the elements you've been carrying has dropped below zero, prepending it to any later subarray makes that subarray smaller. So the moment your running total goes negative, throw it away and restart at the current element — never worse, usually better.

2Aha

Best-ending-here depends only on best-ending-at-previous

Let current be the largest sum of a subarray ending exactly at index i. Then current = max(nums[i], current + nums[i]): either start fresh at nums[i], or extend the previous run. That single recurrence is dynamic programming with one variable instead of a table — the global answer is the max current over all i.

3Aha

Seed with the first element, not zero

Because the subarray is non-empty, initialize both current and best to nums[0] (or -∞), never 0. Seeding with 0 quietly returns 0 for an all-negative array — a subarray that isn't allowed to exist.

Brute force vs optimal

	Sum every window	Divide & conquer	Kadane
Idea	Try all start/end pairs	Best in left, right, or crossing the middle	Running sum, drop when negative
Time	O(n²)	O(n log n)	O(n)
Space	O(1)	O(log n)	O(1)

The full code for all three is in the Approaches selector below.

Summary

Key takeaway

Kadane's algorithm: sweep once keeping current = max(nums[i], current + nums[i]) — the best subarray sum ending here — and track the global best. Drop the running total the instant it turns negative, and seed from nums[0] so the non-empty rule holds for all-negative inputs. O(n) time, O(1) space: dynamic programming folded into a single scan.