Maximum Subarray Sum

Given a list of whole numbers nums, find the run of consecutive items (at least one item long) whose sum is as large as possible. Write max_subarray(nums) that returns that largest sum.

Examples

max_subarray([4, -1, 2, 1, -5, 4])  # returns 6
max_subarray([5, -9, 6, -2, 3])     # returns 7
max_subarray([-3, -1, -2])          # returns -1

In the first example the best run is 4, -1, 2, 1. When every number is negative, the best run is the single largest number.

Constraints

• 1 <= len(nums) <= 10000
• -10000 <= nums[i] <= 10000