Largest Sum of a Subarray | Practice

Given a list of integers nums, return the largest sum of a subarray: a non-empty run of consecutive items.

The list may hold negative numbers. When every number is negative, the answer is the largest single number.

Example 1

Input: nums = [3, -4, 5, -1, 2, -6, 1]
Output: 6

[5, -1, 2] adds up to 6.

Example 2

Input: nums = [-3, -1, -2]
Output: -1

Every number is negative, so the best is the largest one on its own.

Constraints

nums holds 1 to 10⁴ numbers.
−10⁴ ≤ nums[i] ≤ 10⁴

Show the pattern

Greedy, Dynamic programming (1D)

A running total that has dropped below zero can only drag down whatever comes after it, so you can safely drop it and start again: a greedy decision made once per item.

See greedy in a visualiser

Show the approach

Walk along the list keeping running, the largest sum of a subarray that ends at the current position. At each new number x, that subarray either extends the previous one (running + x) or starts afresh at x, whichever is larger; in other words, a negative running total is dropped, because it would only lower everything after it.

Keep best, the largest running seen. Starting both at nums[0] handles lists where every number is negative. This is Kadane's algorithm; it is also the 1D table "best sum ending here", keeping only its last entry.

Time: O(n) · Space: O(1)