(动态规划) LeetCode53. 最大子序和

题目：
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

方法一：贪心
思路：
1、如果sum > 0，sum = sum + nums[i]，否则sum = nums[i]，重新开始计算sum
2、重复上步骤
时间复杂度： O(n)
空间复杂度： O(1)

var maxSubArray = function(nums) {
    let len = nums.length;
    let sum = max = nums[0];
    for(let i = 1, len = nums.length; i < len; i++){
        sum = Math.max(nums[i], nums[i] + sum)
        max = Math.max(max, sum);
    }
    return max;
}; 

方法二：动态规划
思路：
同上
时间复杂度： O(n)
空间复杂度： O(1)

var maxSubArray = function(nums) {
    let max = nums[0];
    for(let i = 1, len = nums.length; i < len; i++){
        if(nums[i - 1] > 0)
            nums[i] = nums[i - 1] + nums[i];
        max = Math.max(max, nums[i]);
    }
    return max;
}; 

方法三：分治法
思路：
1、将问题分解为子问题并递归地解决它们。
1、合并子问题的解以获得原始问题的解。
时间复杂度： O(nlogn)
空间复杂度： O(logn)

var maxSubArray = function(nums) {
     let helper = function(left, right){
        if(left === right)
            return nums[left]
        let p = parseInt((left + right) / 2);
        let l = helper(left, p);
        let r = helper(p + 1, right);
        let c = cross(left, right, p);
        return Math.max(Math.max(l, r), c);
    }

    let cross = function(left, right, p){
        let sum_l = sum_r = 0;
        let max_l = max_r = Number.MIN_SAFE_INTEGER;

        for(let i = p; i >= left; i--){
            sum_l += nums[i];
            max_l = Math.max(max_l, sum_l)
        }
        for(let i = p + 1; i <= right; i++){
            sum_r += nums[i];
            max_r = Math.max(max_r, sum_r)
        }
        return max_l + max_r;
    }
    let len = nums.length;
    return helper(0, len - 1);
   
};