Maximum Subarray Sum

The problem. You are given an integer array nums. Find the contiguous subarray (containing at least one number) with the largest sum, and return that sum.

Example

Input:  nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Why:    the slice [4, -1, 2, 1] adds up to 6, and no other slice does better.

A subarray is a run of neighbouring elements. [4, -1, 2] is a subarray of the example; [4, 2] is not, because it skips the -1 in between.

If every number were positive, the answer would simply be the whole array. The negative numbers are what make this interesting: sometimes a -1 inside a run is worth keeping because the numbers after it pay it back, and sometimes a long negative stretch means you should give up and start again.