Maximum Subarray

Medium#53best subarray

You get an array of whole numbers, some of them negative. Pick a run of one or more neighbouring numbers with the largest sum and return that sum. Our example: [3, -4, 2, -1, 5, -7, 4] — the answer is 6, the run [2, -1, 5].

53 Maximum SubarrayWalkthrough · 1×

Example: [3, -4, 2, -1, 5, -7, 4]. Watch index 2: the run [3, -4] behind it sums to -1, so it is dropped and a new run starts at 2.

numsherebest031-4223-1455-7643
this stepthe run that here sumsread fromdropped by a fresh startanswer

A run that ends at index 0 can only be [3]: here = 3

01/27
restart · back · play · step
Speed
1function maxSubArray(nums):
2 here = nums[0] // best sum of a run that ends at i
3 best = nums[0]
4 for i from 1 to len(nums) - 1:
5 if here < 0:
6 here = nums[i] // start over
7 else:
8 here = here + nums[i]
9 best = max(best, here)
10 return best
state
i
–
here
3
best
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. The best run that ends at index i is nums[i] alone or nums[i] added to the best run that ends at i - 1. Nothing else can end there, so one number, here, carries all that matters from the left.
  2. A run behind with a negative sum only lowers whatever follows it, so the run starts fresh. With a sum of 0 or more it never hurts, so the run grows.
  3. Every run ends somewhere, so the largest here over all indices, kept in best, is the answer. best starts at nums[0], not 0, so an array of only negative numbers still gets its largest number.

Complexity

Time O(n): one pass, a constant amount of work per number. Memory O(1): only here and best; the rows in the picture are there to show their history.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.