[DP]53. Maximum Subarray

53. Maximum Subarray
面试的时候考到了，动态规划最优。O（n）
提升一点小难度，加法变乘法152. Maximum Product Subarray

大神的解析在这里

最大连续子序列和，非常经典的题。

当我们从头到尾遍历这个数组的时候，对于数组里的一个整数，它有几种选择呢？它只有两种选择： 1、加入之前的SubArray；2. 自己另起一个SubArray。

那什么时候会出现这两种情况呢？
如果之前SubArray的总体和大于0的话，我们认为其对后续结果是有贡献的。这种情况下我们选择加入之前的SubArray
如果之前SubArray的总体和为0或者小于0的话，我们认为其对后续结果是没有贡献，甚至是有害的（小于0时）。这种情况下我们选择以这个数字开始，另起一个SubArray。

class Solution {
    public int maxSubArray(int[] nums) {
        if(nums.length == 0) return 0;
        int sumPre = nums[0];
        int globalMax = nums[0];
        for(int i = 1; i< nums.length; i++){
            sumPre = Math.max(sumPre+ nums[i], nums[i]); //continue a subarray, or start a new subarry
            globalMax = Math.max(sumPre , globalMax);//compare with all

        }
       return globalMax;
    }
}

除了DP还可以思考一些其他思路