给定一个整型数组 nums ，找出和最大的连续的子数组（包含至少一个数）并返回。

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

进阶：

如果你找到了O(n)复杂度的解决方案，尝试用更巧妙的分治法来码出另一种解决办法。

解法1:

数组最大子数组和有两种情况，一种是只有非正数的数组，这种情况下解是该数组中值最大的元素。另一种是含有正数的数组，这种情况需要进行累加比较。迭代解法：

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    
    let max = nums[0];
    let sum = 0;
    for(let num of nums) {
        
        if (sum >= 0) {
            sum += num;
        } else {
            sum = num;
        }
        
        if (sum > max) max = sum;
    }
    return max;
};

解法2:

分治法。在数组中任取一点作为基点（为了提高效率，一般取中点），那么所求解有三种情况：存在于基点左边的子数组中、存在于基点右边的子数组中和存在于横跨基点(以基点为基础向左右两边取最大)左右两边的子数组中。递归解法：

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) { 
    function findMax(arr, low, base, high) {
        let lMax = arr[base];
        let rMax = arr[base + 1];
        for (let i = base, sum = 0; i >= low; i--) {
          sum += arr[i];
          if (sum > lMax) lMax = sum;
        }
        for (let i = base + 1, sum = 0; i <= high; i++) {
          sum += arr[i];
          if (sum > rMax) rMax = sum;
        }
        return lMax + rMax;
    }
    
    function findSubMax(arr, begin, end) { 
        if (begin == end) return arr[begin];
        let mid = parseInt(end - (end - begin) / 2);
        let leftSum = findSubMax(arr, begin, mid);
        let rightSum = findSubMax(arr, mid + 1, end);
        let midSum = findMax(arr, begin, mid, end);
        return Math.max(leftSum, rightSum, midSum);
    }
    return findSubMax(nums, 0, nums.length - 1);
};