53. 最大子序和

[swiftwind0405]

方法一：贪心 / 动态规划

解题思想：
若前一个元素大于0，则将其加入到当前元素上。
最后结果既是这个加上的值的最大值。
为什么前面的小于0就丢了，因为如果这个数组都是正数，一直加下去就可以了。没有什么最大子序和，最大就是他自己。

贪心，前面的小于0，就丢了。动态规划，前面的元素大于0，就和当前元素相加。

那贪心和动态规划的区别是什么呢？？

动态规划的是首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 ans
如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字
如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字
每次比较 sum 和 ans的大小，将最大值置为ans，遍历结束返回结果

代码：

var maxSubArray = function(nums) {
    // 初始值为0,最大值为第一个无素。
    let pre = 0, maxAns = nums[0];
    nums.forEach((x) => {
        // 前一个元素加到当前元素上，取较大值
        pre = Math.max(pre + x, x);
        // 取结果的最大值
        maxAns = Math.max(maxAns, pre);
        console.log(pre, maxAns)
    });
    return maxAns;
};

复杂度分析：

• 时间复杂度：O(n)，只遍历了数组一次。
• 空间复杂度：O(1)，只用了常数级的存储空间。

方法二：分治

TODO