Greedy: maximum subarray (Kadane)

You're handed a list of numbers (some negative) and asked for the largest sum you can get from a contiguous run of them. Brute force would try every start/end pair — O(n^2). Kadane's algorithm does it in a single pass with a tiny greedy insight:

As you walk left to right, the best subarray ending here is either this element alone, or this element glued onto the best subarray ending at the previous spot — whichever is bigger.

If the running total ever goes negative, dragging it forward only hurts, so you greedily drop it and start fresh from the current element.

cur = best = nums[0]
for x in nums[1:]:
    cur = max(x, cur + x)   # extend, or restart at x
    best = max(best, cur)

Because the subarray must be non-empty, seed both trackers with the first element (this also handles all-negative inputs correctly).

Your task

Write max_subarray(nums) returning the maximum sum of any contiguous, non-empty subarray. nums always has at least one element.

max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4])   # 6   (the run [4, -1, 2, 1])
max_subarray([1])                                # 1
max_subarray([5, 4, -1, 7, 8])                   # 23  (the whole list)
max_subarray([-1, -2, -3])                       # -1  (least-bad single element)

Hint: keep cur (best sum ending at the current index) and best (best seen so far). Never let the answer be "empty".