题目

给定一个数组arr，返回子数组的最大累加和。

例如，arr=[1,-2,3,5,-2,6,-1],所有的子数组中，[3,5,-2,6]可以累加出最大的和12，所以返回12.

解答

如果arr中没有正数，产生的最大累加和一定是数组中的最大值。

如果arr中有正数，从左到右遍历arr，用变量cur记录每一步的累加和，遍历到正数cur增加，遍历到负数cur减少。当cur<0时，说明累加到当前数出现了小于0的结果，那么累加的这一部分肯定不能作为产生最大累加和的子数组的左边部分，此时令cur=0，表示重新从下一个数开始累加。当cur>0时，每依次累加都可能是最大的累加和，所以，用另外一个变量max全程跟踪记录cur出现的最大值即可。

例如，arr=[1,-2,3,5,-2,6,-1],开始时，max=极小值，cur=0。

遍历到1，cur=cur+1=1，max更新成1。遍历到-2，cur=cur-2=-1，开始出现负的累加和，所以说明[1,-2]这一部分肯定不会作为产生最大累加和的子数组的左边部分，于是令cur=0，max不变。遍历到3，cur=cur+3=3，max更新成3.遍历到5，cur=cur+5=8，max更新成8。遍历到-2，cur=cur-2=-6，虽然累加了一个负数，但是cur依然大于0，说明累加的这一部分（也就是[3,5,-2]）仍可能作为最大累加和子数组的左边部分。max不更新。遍历到6，cur=cur+6=12。遍历到-1，cur=cur-1=11，max不更新。最后返回12。cur累加成为负数就清零重新累加，max记录cur的最大值即可。

public int maxSum(int[] arr){if(arr == null || arr.length ==0){return 0;}int max = Integer.MIN_VALUE;int cur = 0;for(int i = 0; i!= arr.length;i++){cur += arr[i];max = Math.max(max,cur);cur = cur < 0 ? 0 : cur;}return max;
}