题目

求一个数组的两个子数组的最大累加和，其中这两个数组不能有重复元素。
[算法原型]http://www.jianshu.com/p/c5eaf8417fc8

思路

1. 已经有了求解数组的最大子数组累加和问题的算法，那么这样想，我对原数组设断点，假设i为断点，容易得到[0,i]和(i,n-1]的最大累加和，这两个累加和加起来就是以i为断点的最大累加和。现在我让这个断点为0,1,2，，，，n-2,每个都会得到一个最大值，求出这些最大值中的最大值就是所求的两个子数组的最大累加和。
2. 直观的想法是两个for循环，外部控制断点移动，内部求解两个子数组最大和，但是这复杂度太高。
3. 回想我们求解子数组最大累加和问题时使用的res,其实res就是记录了[0,i]的最大累加和，所以使用一个辅助数组，记录下res,遍历两次（从前往后，从后往前）就可以求解。
4. 实际上，由于我们最后的求解顺序就是从前往后，所以可以只使用一个辅助数组就可以了。

算法流程&原理

1. 使用一个辅助数组r,r[i]表示从[i,n-1]这个数组的子数组的最大累加和，可以很容易求得r.
2. 从头开始遍历，使用一个变量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;
    }