题解 | #连续子数组的最大和#
连续子数组的最大和
http://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484
思路
核心点在于理解到：若前面部分的和 < 0，说明前面的部分对于计算总和这件事来说只会拖后腿，那么便舍弃掉，将计算当前sum的起点重设为0。但同时要一直更新当前的最大和值
代码
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
int maxSum = Integer.MIN_VALUE; // 因为有负数，所以不能设为0
int curSum = 0;
for(int i = 0;i < array.length;i++){
curSum += array[i];
maxSum = Math.max(maxSum,sum);
if(curSum < 0) curSum= 0;
}
return maxSum; // 核心！！若小于0，则计算和的起点重新置为0
}
}
