Maximum Subarray

A subarray is a run of neighbouring elements of a list, taken without gaps. Among all the non-empty subarrays of a list of integers, you want the one whose elements add up to the most, and you return that sum.

In [2, -4, 3, -1, 5, -6, 1] the best run is [3, -1, 5], with a sum of 7. It keeps the -1 because the 5 after it more than pays for it, and it leaves out the 2 at the start because the -4 that follows costs more than the 2 brings.

The classic one pass solution is Kadane's algorithm. Walk through the list and keep the best sum of a run that ends at the current element. At each element there are only two choices: extend the run that ended at the previous element, or restart with a new run that begins here. Extending pays off only while the earlier run has a positive sum; once that sum drops to zero or below, carrying it along can only hurt, so you start fresh. The answer is the largest run sum seen anywhere along the way.

For the example, the best run sums ending at each position are 2, -2, 3, 2, 7, 1 and 2, so the answer is 7. Every element is looked at once, so the work grows linearly with the length of the list.

Write a function named maxSubArray that gets a list of integers nums and returns the largest sum of a contiguous, non-empty subarray of nums.

Constraints: 1 ≤ nums.length ≤ 10^5, -10^4 ≤ nums[i] ≤ 10^4.