题目
求一个数组的两个子数组的最大累加和，其中这两个数组不能有重复元素。
[算法原型]http://www.jianshu.com/p/c5eaf8417fc8
思路
- 已经有了求解数组的最大子数组累加和问题的算法，那么这样想，我对原数组设断点，假设i为断点，容易得到[0,i]和(i,n-1]的最大累加和，这两个累加和加起来就是以i为断点的最大累加和。现在我让这个断点为0,1,2，，，，n-2,每个都会得到一个最大值，求出这些最大值中的最大值就是所求的两个子数组的最大累加和。
- 直观的想法是两个for循环，外部控制断点移动，内部求解两个子数组最大和，但是这复杂度太高。
- 回想我们求解子数组最大累加和问题时使用的res,其实res就是记录了[0,i]的最大累加和，所以使用一个辅助数组，记录下res,遍历两次（从前往后，从后往前）就可以求解。
- 实际上，由于我们最后的求解顺序就是从前往后，所以可以只使用一个辅助数组就可以了。
算法流程&原理
- 使用一个辅助数组r,r[i]表示从[i,n-1]这个数组的子数组的最大累加和，可以很容易求得r.
- 从头开始遍历，使用一个变量res记录[0，i]的子数组的最大累加和，另外，这一过程中使用一个全局最大total记录[0,i]和(i,n-1]两个数组的最大子数组的和，更新total。遍历结束后total即为两个无重复子数组的最大累加和。
代码
public static int maxSum(int[] arr){
if(arr==null||arr.length<2)
return 0;
int[] r=new int[arr.length];
r[r.length-1]=arr[arr[arr.length-1]];
int cur=arr[arr.length-1];
for(int i=arr.length-2;i>0;i--){
cur=cur<0?0:cur;
cur+=arr[i];
r[i]=Math.max(cur,r[i+1]);
}
cur=arr[0];
int res=0;
int total=arr[0]+r[1];
for(int i=1;i<arr.length-1;i++){
cur=cur<0?0:cur;
cur+=arr[i];
res=Math.max(cur,res);
total=Math.max(total,res+ r[i+1]);
}
return total;
}
