題目

給定一個數組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;
}