#307 Maximum Subarray

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

Rules:

• Subarray must be contiguous (elements next to each other)
• Subarray must be non-empty
• Array can contain negative numbers

Constraints:

• 1 ≤ nums.length ≤ 1000
• -1000 ≤ nums[i] ≤ 1000

Examples:

// Example 1:
console.log(maxSubArray([2, -3, 4, -2, 2, 1, -1, 4]));
// Output: 8
// Explanation: Subarray [4,-2,2,1,-1,4] sums to 8

// Example 2:
console.log(maxSubArray([-1]));
// Output: -1
// Explanation: Single element array, -1 is the only sum