Given a list of integers nums, return the largest sum of any non-empty contiguous run of elements.
Implement max_subarray(nums: list[int]) -> int.
max_subarray([3, -4, 5, -1, 2, -6, 1]) # 6 (5 - 1 + 2)
max_subarray([-7, -2, -9]) # -2 (must pick at least one element)
max_subarray([4]) # 4
Constraints: 1 <= len(nums) <= 10^5, -10^4 <= nums[i] <= 10^4.
Checking every (start, end) pair is O(n²), too slow here; aim for O(n).
Show hint
Scan left to right, tracking the best sum of a run that ends at the current index: it either extends the previous such run or starts fresh here. Watch out for all-negative input.