Maximum subarray sum in O(n)?

Kadane's algorithm

Kadane's idea: walk through the array keeping cur, the best sum of a subarray that ends at the current position.

At each number x, either extend the previous subarray (cur + x) or start fresh at x, whichever is bigger. Track the best cur ever seen.

One pass, O(n) time, O(1) memory.

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

Kadane: extend or restart at each element.