題目
求一個(gè)數(shù)組的兩個(gè)子數(shù)組的最大累加和五辽，其中這兩個(gè)數(shù)組不能有重復(fù)元素垛膝。
[算法原型]http://www.reibang.com/p/c5eaf8417fc8
思路
- 已經(jīng)有了求解數(shù)組的最大子數(shù)組累加和問(wèn)題的算法育八，那么這樣想甜紫，我對(duì)原數(shù)組設(shè)斷點(diǎn)凳谦，假設(shè)i為斷點(diǎn)驹尼，容易得到[0,i]和(i,n-1]的最大累加和，這兩個(gè)累加和加起來(lái)就是以i為斷點(diǎn)的最大累加和⊥砬辏現(xiàn)在我讓這個(gè)斷點(diǎn)為0,1,2峰伙，堂鲜，主巍，弛房，n-2,每個(gè)都會(huì)得到一個(gè)最大值疲憋，求出這些最大值中的最大值就是所求的兩個(gè)子數(shù)組的最大累加和遣臼。
- 直觀的想法是兩個(gè)for循環(huán)，外部控制斷點(diǎn)移動(dòng)怒医，內(nèi)部求解兩個(gè)子數(shù)組最大和岭埠，但是這復(fù)雜度太高。
- 回想我們求解子數(shù)組最大累加和問(wèn)題時(shí)使用的res,其實(shí)res就是記錄了[0,i]的最大累加和音榜，所以使用一個(gè)輔助數(shù)組庞瘸，記錄下res,遍歷兩次（從前往后，從后往前）就可以求解赠叼。
- 實(shí)際上擦囊，由于我們最后的求解順序就是從前往后，所以可以只使用一個(gè)輔助數(shù)組就可以了嘴办。
算法流程&原理
- 使用一個(gè)輔助數(shù)組r,r[i]表示從[i,n-1]這個(gè)數(shù)組的子數(shù)組的最大累加和瞬场，可以很容易求得r.
- 從頭開(kāi)始遍歷，使用一個(gè)變量res記錄[0涧郊，i]的子數(shù)組的最大累加和贯被，另外，這一過(guò)程中使用一個(gè)全局最大total記錄[0,i]和(i,n-1]兩個(gè)數(shù)組的最大子數(shù)組的和妆艘，更新total刃榨。遍歷結(jié)束后total即為兩個(gè)無(wú)重復(fù)子數(shù)組的最大累加和。
代碼
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;
}
