[DP]53.|[DP]53. Maximum Subarray [DP]53.MaximumSubarray

53. Maximum Subarray
面试的时候考到了，动态规划最优。O（n）
提升一点小难度，加法变乘法152. Maximum Product Subarray
【[DP]53.|[DP]53. Maximum 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还可以思考一些其他思路