Practice - Maximum Subarray

Given an integer array $nums$, find the contiguous subarray with the largest sum and return its sum.

For example, if $nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]$, the answer is $6$ (subarray $[4, -1, 2, 1]$).

Hint: at each position, decide whether to extend the current subarray or start a new one. This uses algebraic comparison: is $current + nums[i]$ better than just $nums[i]$?