The tell: Best contiguous run under a sum, with negatives present.
How you get there
1At each element decide: extend the current run, or start fresh from this element.
2That decision is max(x, current + x) — Kadane's algorithm.
3Track the best seen separately, because the running value can dip below it.
Solution
Python
def max_subarray(nums: list[int]) -> int:
best = current = nums[0]
for x in nums[1:]:
current = max(x, current + x)
best = max(best, current)
return best
Time
O(n)
Space
O(1)
What goes wrong
Initialising best to 0 returns 0 for an all-negative array instead of the largest single element.