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.

In plain steps (you write the Python):

cur = best = first element
for each later element x:
    cur  = the bigger of (x by itself) and (x added onto cur)   # extend or restart
    best = the bigger of (best so far) and (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".