Kadane's Algorithm

The Idea

Walk the array keeping the best sum that ends at the current element. If carrying the running sum forward hurts more than starting over, throw it away and restart here. The answer is the largest value that streak ever reached.

Real-World Example

A shop tracking daily profit and loss wants its strongest stretch of trading. Once a run has dug the total deep into the red, dragging it into the next good days only hides them, so the tally starts again.

The Code

def max_subarray(nums):
    best = current = nums[0]
    for x in nums[1:]:
        # extend the current streak, or restart at x
        current = max(x, current + x)
        best = max(best, current)
    return best

print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))   # 6
# the winning stretch is [4, -1, 2, 1]

nums = [2, -1, 3]
best = cur = nums[0]
for x in nums[1:]:
  cur = max(x, cur + x)
  best = max(best, cur)
print(best)