【题目】
给定一个数组arr,返回子数组的最大累加和。
例如，arr[1,-2,3,5,-2,6,-1],所有的子数组中，[3,5,-2,6]可以累加出最大的和12，所以返回12.
【要求】
如果arr长度为N，要求时间复杂度为O(N)，额外空间复杂度为O(1).
【思路】
如果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,max更新成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;
}
