最大連續(xù)子序列問題
問題定義：
給定K個整數(shù)的序列{ N1, N2, ..., Nk }应闯，其任意連續(xù)子序列可表示為{ Ni, Ni+1, ..., Nj }枪狂，其中 1 <= i <= j <= K嗓袱。最大連續(xù)子序列是所有連續(xù)子序列中元素和最大的一個宏胯， 例如給定序列{ -2, 11, -4, 13, -5, -2 }渔嚷，其最大連續(xù)子序列為{ 11, -4, 13 }谨湘，最大和為20
解法1：樸素解法, 時間復雜度 O(K^2)
//假設(shè)給定序列：a1,a2,...,aK
maxsum=0; // 最大的連續(xù)子序列的和
for(int i=0; i<K; i++){
tmpSum=0;
for(int j=i; j<K; j++){
tmpSum += a[j]
if(tmpSum > maxsum){
maxsum = tmpSum;
}
}
}
解法2：分治算法, 時間復雜度：O(nlogn)
對于任意一個序列{a1, a2, ...,am,.... an}, ( m=(n+1)/2 ) 最大的連續(xù)子序列在該序列中的位置存在三種情況:
- 位于中間部分的左邊;
- 位于中間部分的右邊 ;
- 左邊和右邊都含有最大的連續(xù)子序列的一部分, e.g. ai, ..., am, ...., aj.
對于情況1,2, 使用遞歸算法可以輕松計算出谚鄙；對于情況3各拷， 則通過求出前半部分的最大和（包含前半部分的最后一個元素）以及后半部分的最大和（包含后半部分的第一個元素）而得到，然后將這兩個和加在一起闷营， 最后烤黍，三種情況中最大的結(jié)果就是要求的結(jié)果。
int MaxSubSum(const int A[], int Left, int Right)
{
int MaxLeftSum,MaxRightSum;
int MaxLeftBorderSum,MaxRightBorderSum;
int LeftBorderSum,RightBorderSum;
int mid,i;
if(Left == Right) // 處理只有一個元素的子序列
{
if(A[Left] > 0)
return A[Left];
else // 對于小于等于0的元素傻盟，
return 0;
}
mid= (Left + Right)/2;
// 情況1
MaxLeftSum = MaxSubSum(A,Left,mid);
// 情況2
MaxRightSum = MaxSubSum(A,mid+1,Right);
// 情況3
MaxLeftBorderSum = 0;
LeftBorderSum = 0;
for(i = mid;i >= Left;i--)// 求解最大序列的左邊部分
{
LeftBorderSum += A[i];
if(LeftBorderSum > MaxLeftBorderSum)
MaxLeftBorderSum = LeftBorderSum;
}
MaxRightBorderSum = 0;
RightBorderSum = 0;
for(i = mid+1;i <= Right;i++)// 求解最大序列的右邊部分
{
RightBorderSum += A[i];
if(RightBorderSum > MaxRightBorderSum)
MaxRightBorderSum = RightBorderSum;
}
return Max(MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum); // 返回三種情況中最大的結(jié)果
}
解法3： 動態(tài)規(guī)劃 , 時間復雜度O(n)
引理1： 以負數(shù)開頭的子序列不會是最大子序列速蕊。
證明：令子序列為{ai, ..., aj}, 其中開頭的元素 ai < 0, 則 ai + ... + aj < ai+1+...+aj 顯然成立。
引理2：對子序列 {ai, ..., aj} , 如果該子序列滿足兩個條件：
- 如果對x取 [i, j) 中的任意整數(shù)(包含i,不包含j) sum{ai, ..., ax} >0.
- sum{ai, ..., aj}<0.
則以該子序列中的任何元素ap開頭的以aj為終結(jié)的任意子序列的和必定小于0娘赴。
證明：從兩個條件中易推斷出:aj<0, 且由引理1知 以負數(shù)開頭的連續(xù)子序列不可能是最大連續(xù)子序列规哲，則： ai > 0.
顯然有 0 >= sum{ai, ..., aj} >= sum{ai-1, ..., aj} >= sum{ap, ..., aj}, 其中 p 是[i, j)之間的整數(shù)。
反證法：假設(shè)sum{ap, ..., aj}>0, p取 [i, j) 之間的整數(shù), 由引理2條件 sum{ai, ..., aj}<0 得出sum{ai, ..., ap-1}<0筝闹，該結(jié)論違反了引理2中的條件：如果對x取[i, j)中的任意整數(shù)(包含i,不包含j) sum{ai, ..., ax} >0. 得證媳叨。
由引理1可知，若a[i]<0, 則應(yīng)跳到a[i+1]作為子序列的開頭元素（如果a[i+1]>0）;
由引理2可知关顷， 若a[i]+...+a[j]<=0且滿足引理2的第一個條件糊秆，則應(yīng)以a[j+1]作為最大連續(xù)子序列的開頭元素(如果a[j+1]>0). 實質(zhì)上，引理1是引理2的特例议双。
引理1和2可歸結(jié)為該狀態(tài)方程： maxsum(i)= max( maxsum(i-1)+ary(i), ary(i) ); （也可以由動態(tài)規(guī)劃方法處理的準則：最優(yōu)子結(jié)構(gòu)”痘番、“子問題重疊”、“邊界”和“子問題獨立”得到）
通過對給定序列順序地反復運用引理1和引理2平痰，最終可求得該序列的最大連續(xù)子序列汞舱。
代碼如下：
int maxSubSeq(int[] ary){
int maxsum=0;
int localSum=0;
for (int i=0; i<ary.length; ++i){
localSum += ary[i];
if(localSum > maxsum){
maxsum= localSum;
}else if (localSum < 0){
localSum=0; // 不考慮 ai~aj中的元素作為子序列的開頭, 其中ai>0, aj<0
} //else ==> localSum >0, 就是引理2中的條件1
}
return maxsum;
}
注意：解法2對于數(shù)組中全部是負數(shù)的數(shù)組返回0，而不是數(shù)組中的最大值宗雇。
解法4:動態(tài)規(guī)劃(可以處理數(shù)組中全部是負數(shù)的情況昂芜，該方法會返回數(shù)組中的最大值)
從解法2的分治思想得到提示,可以考慮數(shù)組的第一個元素A[0], 以及和最大的一段數(shù)組(A[i], .., A[j]), A[0] 和 和最大的一段數(shù)組的關(guān)系如下：
- 當0=i=j時，元素A[0]自己構(gòu)成和最大的一段赔蒲。
- 當0=i<j時泌神，元素和最大的一段數(shù)組以A[0]開頭A[j]結(jié)尾良漱。
- 當0 < i時，元素和和最大的一段數(shù)組沒有關(guān)系欢际。
因此母市，我們將一個大問題（具有N個元素的數(shù)組）轉(zhuǎn)換成較小的問題（具有N-1個元素的數(shù)組）
記 all[1] 為 A[1],...,A[N-1]中 和最大的一段數(shù)組之和
記 start[1] 為 A[1], ..., A[N-1]中 以A[1]開頭的和最大的一段數(shù)組之和
不難發(fā)現(xiàn)，(A[0], A[1], ..., A[N-1]) 中和最大的一段數(shù)組的和 是 三種情況的最大值 max(A[0], A[0]+start[1], all[1])
可以看出該問題無后效性损趋，可以使用動態(tài)規(guī)劃的方案解決患久。
因此我們可以得到初始的算法：
public static int maxSum1(int[] A){
int[] start = new int[A.length];
int[] all = new int[A.length];
all[A.length-1] = A[A.length-1];
start[A.length-1] = A[A.length - 1];
for(int i = A.length-2; i>=0; --i){
start[i] = Math.max(A[i], A[i] + start[i+1]);
all[i] = Math.max(start[i], all[i+1]);
}
return all[0];
}
算法優(yōu)化
可以看到，計算start[i] 時浑槽，和 start[i+1]有關(guān)蒋失，計算all[i] 時，和all[i+1]有關(guān)
因此括荡，我們可以使用兩個變量進行優(yōu)化高镐。
public static int maxSum1(int[] A){
int nStart = A[A.length-1];
int nAll = A[A.length-1];
for(int i = A.length-2; i>=0; --i){
nStart = Math.max(A[i], A[i] + nStart);
nAll = Math.max(nStart , nAll);
}
return nAll;
}
從上述優(yōu)化算法可以看出：當nStart < 0時溉旋，nStart被賦值為A[i].
因此我們可以將算法改寫為更清晰的寫法：
public static int maxSum(int[] A){
int nStart = A[A.length-1];
int nAll = A[A.length - 1];
for(int i = A.length-2; i>=0; --i){
if(nStart < 0){
nStart = 0;
}
nStart += A[i];
if(nStart > nAll){ /// 即使數(shù)組中全部是負數(shù)畸冲，我們也會選出具有最大值的數(shù)。
nAll = nStart;
}
}
return nAll;
}
擴展問題
問題1
如果數(shù)組(A[0], ..., A[n-1])首尾相連观腊，即我們被允許找到一段數(shù)字(A[i],..., A[n-1], A[0], ..., A[j])式其和最大邑闲。
問題分解:
- 解沒有穿過A[n-1]和A[0]連接
- 解穿過了A[n-1]和A[0]連接
2.1. 解包含A[0], ..., A[n-1]
2.2. 解包含兩部分：(1)從A[0]開始的一段 (A[0], ..., A[j]) (0<=j <n); (2) 從A[i]開始的一段(A[i], .., A[n-1]) (j<i<n)
尋找2.2.的解 相當于 從A數(shù)組中刪除一塊子數(shù)組（A[j+1],....,A[i-1]）且刪除的子數(shù)組的和是負數(shù)且其絕對值最大。這相當于將問題轉(zhuǎn)為子問題1梧油。
問題的解：取兩種情況的最大值苫耸。
時間復雜度 ：求解子問題2只需遍歷數(shù)組一次，子問題1可以使用前面介紹的方法求解時間復雜度O(N). 所以時間復雜度共O(N)
代碼：（該代碼尚未驗證其正確性儡陨，請讀者自行驗證褪子，如有錯誤請留言評論）
/**
* The correctness should be validated in the future!!!
* @param A
* @return
*/
public static int maxSumCycle(int[] A){
int s1 = maxSum(A);
int s2 = 0;
int nAll = A[A.length-2];
int nStart = A[A.length-2];
for(int i=A.length-1; i>=0; --i){
s2 += A[i];
// Find maximum abs value from range 1~A.length-2
if(i>=1 && i<=A.length-3){
nStart = Math.min(nStart, A[i] + nStart);
nAll = Math.min(nStart, nAll);
}
}
if(nAll>0) nAll = 0;
return Math.max(s1, Math.max(s2, s2 + nAll));
}
問題2
如果要求通知返回最大子數(shù)組的位置，應(yīng)該如何修改算法骗村，使保持O(N)的復雜度?
public static int maxSum(int[] A){
int s=A.length-1, e=A.length-1; // [s, e]
int p =0;
int nStart = A[A.length-1];
int nAll = A[A.length - 1];
for(int i = A.length-2; i>=0; --i){
if(nStart < 0){ // 以 A[i+1] 開頭的子數(shù)組的和嫌褪，不可能是最優(yōu)解，新的最優(yōu)解的終點應(yīng)該是 A[i]
nStart = 0;
p = i;
}
nStart += A[i];
if(nStart > nAll){
if(nStart==A[i]) e = p; // 表明以p為終點的最優(yōu)解 開始計算胚股。
nAll = nStart;
s = i; // 如果 nStart > nAll, 說明以當前 A[i] 開始一段數(shù)組笼痛，具有目前最優(yōu)的解。
}
}
System.out.printf("sidx=%d, eidx=%d\n", s, e);
return nAll;
}
//測試實例琅拌，讀者可自行實驗缨伊，推導
// int[] ary = {1, -2, 3, 10, -4, 7, 2, -5};
// int[] ary = {0, -2, 3, 5, -1, 2};
// int[] ary = {-9, -2, -3, -5, -3};
// int[] ary = {1, -2, 3, 5, -3, 2};
注：解法4和擴展問題，都是引用《編程之美》上面的解法进宝。
