53. Maximum Subarray

MediumGreedy AlgorithmsGreedy / DP over subarray sumsRunning best-ending-here (Kadane)

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.

Open official problem prompt ↗

In plain English

Locate the single contiguous stretch of the array whose elements add up to the greatest possible total.

Picture it like this

Like walking a trail tracking your net elevation gain: if your accumulated climb ever drops below zero it is deadweight, so you reset your baseline at your feet and keep noting the highest point you have ever stood.

Example

Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Why: The subarray [4, -1, 2, 1] has the largest sum, 6.

Constraints

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

Pattern lesson

See the pattern, then code

Running best-ending-here (Kadane)

↗

Greedy Algorithms

A locally best action can be justified by an exchange argument or invariant.. A prefix of negative running sum can only hurt what follows, so whenever the best sum ending at the previous position is negative, discard it and start fresh at the current element.

New words, made simpleKnow these before the algorithm

best-ending-here (cur): The largest sum of any subarray that ends exactly at the current index.
global best: The largest best-ending-here value seen across all indices so far.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Brute force all subarrays

Too slow at n = 10^5.

Try every start/end pair and sum each subarray.

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

Divide and conquer

Elegant but slower and heavier than necessary.

Recursively combine best-left, best-right, and best-crossing sums.

Time O(n log n)Space O(log n)

Best choiceKadane's scan

Linear, constant space, single pass.

Carry a running best-ending-here, restarting whenever it turns negative, and track the max.

Time O(n)Space O(1)

The rule we keep true

Invariant

After processing index i, cur equals the maximum subarray sum ending at i, and best equals the maximum subarray sum over any subarray ending at or before i.

Why this is correct

Reasoning

Any optimal subarray ends at some index i; its sum equals the best-ending-here at i, which Kadane computes exactly via max(x, cur + x). Taking the maximum of these over all i therefore yields the global optimum.

The algorithm in three movesSay these aloud before coding

1Initialize both the best-ending-here and the global best to nums[0]

cur=4 best=4 (restart at 4)

2For each later value, extend the previous run or restart at the value, whichever is larger

cur=3,5,6 best climbs to 6

3Update the global best with the new best-ending-here

cur dips but best stays 6

4Return the global best

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

-20

-32

-14

-57

1 · Readnums[0]=-2

2 · AskSeed values?

3 · Update statebest=-2, cur=-2

4 · ResultStart comparisons from index 1.

Key takeaway

The window [4,-1,2,1] is where the running sum peaks at 6 before a large negative resets it.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 2Seed with first element
Because the subarray must be non-empty, both trackers start at nums[0] rather than 0.
2
Lines 3-4Extend-or-restart
cur = max(x, cur + x) drops any negative prefix that would only shrink the total.
3
Lines 5Record the peak
best captures the largest running sum witnessed so far.
4
Lines 6Answer
best is the maximum subarray sum once every index has been considered.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

All-negative arrays return the largest (least negative) single element
A single-element array returns that element
Arrays where the whole array is optimal

Common beginner mistakes

Initializing best to 0, which is wrong for all-negative inputs since the subarray must be non-empty
Resetting cur to 0 instead of to x, breaking the all-negative case
Forgetting to update best after updating cur

Check your understanding

Why start best at nums[0] rather than 0 or negative infinity is fine too?

Maximum Subarray

Maximum Subarray

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Greedy Algorithms