Example 1
ready- Input
nums = [ -2, 1, -3, 4, -1, 2, 1, -5, 4 ]- Expected
6- Why
- the run [4, -1, 2, 1] sums to 6
Maximum Subarray
35 min · maxSubArray()mediumOpen in LeetCode #53 ↗
A single rough day can be worth keeping when the stretch around it is strong enough.
Given an integer array nums, return the largest sum made by one contiguous subarray,
a non-empty run of neighboring elements with no gaps.
The chosen run may contain one element or the entire array. It must not be empty, so an
all-negative input returns its least-negative single value rather than 0.
Constraints
1 <= nums.length <= 100_000-10_000 <= nums[i] <= 10_000- Every possible subarray sum fits in a signed 32-bit integer.
Hints
Start with every left edge
Fix a starting index and extend the right edge one position at a time, updating the sum as you go. This gives an honest O(n²) baseline.
What must end here?
For each index i, track the best non-empty subarray that ends exactly at i.
It either starts at nums[i] or extends the best ending at i - 1.
Don't default to zero
Initialize both running values from nums[0]. Starting from zero accidentally
allows an empty subarray and breaks every all-negative input.
Follow-up
Can you return the start and end indices of a maximum-sum subarray while keeping O(1) extra space?
Visible cases
Examples
Example 2
ready- Input
nums = [ 1 ]- Expected
1- Why
- the only non-empty subarray contains the one value
Example 3
ready- Input
nums = [ -3, -1, -2 ]- Expected
-1- Why
- empty isn't allowed, so the largest single value wins
Interview signal
Asked at
AmazonGoogleMetaBloomberg
Enumerate every subarray
Choose each starting index, then extend the ending index while carrying the running sum. Updating the sum avoids a third loop.
def max_sub_array(nums: list[int]) -> int:
best = nums[0]
for start in range(len(nums)):
total = 0
for end in range(start, len(nums)):
total += nums[end]
best = max(best, total)
return bestThere are n(n + 1) / 2 non-empty subarrays, and this version inspects every one.
Time O(n²). Space O(1).
Kadane's algorithm
Kadane's algorithm is the rolling dynamic program that keeps the best subarray ending at the current position. Its DP pieces are:
- State:
ending[i]is the largest sum of a non-empty subarray ending exactly at indexi. - Transition:
ending[i] = max(nums[i], ending[i - 1] + nums[i]). Start fresh ati, or extend yesterday's best ending. - Base case:
ending[0] = nums[0].
Why is resetting safe? If the best sum ending before i is negative, attaching it
would make every subarray starting at i worse. No future element can repair that
loss better than starting from the same future element without the negative prefix.
The transition needs one previous state, while best remembers the strongest state
seen anywhere.
def max_sub_array(nums: list[int]) -> int:
current = nums[0]
best = nums[0]
for value in nums[1:]:
current = max(value, current + value)
best = max(best, current)
return bestInitializing from nums[0] enforces the non-empty rule. With all-negative input,
current repeatedly chooses the least harmful single element, and best captures
the largest one.
Time O(n). Space O(1).
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
6
Run: visible + custom · Submit: full suite