Largest sum of a run

mediumGreedy choiceDynamic programming, 1D target 25 min

Largest sum of a run

Not solved yetLeetCode 53. Maximum Subarray

A subarray, which we also call a run, is one or more neighboring items of a list, in order, with no gaps. In [4, -1, 2], both [4, -1] and [-1, 2] are subarrays, but [4, 2] is not.

You get a list of integers nums. Every subarray of it has a sum. Return the largest of those sums. A subarray holds at least one item, so when every number is negative the answer is the largest single number, not 0.

Example 1

Inputnums = [2, -3, 4, -1, 2, -5, 3]Output5

The subarray [4, -1, 2] adds up to 5. Crossing the -1 to reach the 2 pays off; crossing the -5 to reach the 3 does not.

Example 2

Inputnums = [-4, -2, -7]Output-2

Every sum is negative, so the best is the largest single number.

Example 3

Inputnums = [5, -2, 6]Output9

The whole list: the dip of -2 costs less than the 6 it reaches.

Constraints

1 ≤ len(nums) ≤ 10⁵
-10⁴ ≤ nums[i] ≤ 10⁴

Plan it first

Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.

Walk In what order will you visit the input?Notebook What will you write down as you go?Promise What stays true after every step?Cost Time and space, in Big O.

Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.

Same pattern