Data structures problem 19 of 30

Maximum subarray

Data structures
Medium

Write max_subarray(nums) that returns the largest sum of any non-empty run of consecutive items. The list may contain negative numbers.

max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4])   # 6  (4, -1, 2, 1)
max_subarray([-3, -1, -2])                       # -1

Show hint

At each position, the best run ending there either extends the best run ending at the previous position, or starts fresh at this item.

Show solution

def max_subarray(nums):
    best = current = nums[0]
    for n in nums[1:]:
        current = max(n, current + n)
        best = max(best, current)
    return best

This is Kadane's algorithm. If the run so far has a negative total, it can only hurt, so drop it and start again at n. One pass, O(n) time, O(1) space. Starting best at nums[0] rather than 0 makes the all-negative case correct.

Want a problem like this every day? See today's problem and keep a streak going.