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还可以思考一些其他思路
