一種改進的最大m子段和算法設計*

廖作斌

(泉州師范學院 數(shù)學與計算機科學學院，福建 泉州 362000)

最大m子段和問題是ACM/ICPC程序設計競賽典型而且常見的算法題型，其描述如下：給定由n個整數(shù)(可能為負)組成的序列a1，a2，a3，……，an，以及一個正整數(shù)m，要求確定序列的m個不相交子段，使這m個子段的總和最大！亦即，給定n個整數(shù)求這n個數(shù)劃分成互不相交的m段的最大m子段和。

最大m子段和的經(jīng)典動態(tài)規(guī)劃優(yōu)化方法是：設b(i, j)表示前i個數(shù)劃分成j段，且包括第i個數(shù)的最大m子段和，那么有狀態(tài)轉移方程：

b[i][j]=max{b[i-1][t],b[i][j-1]}+a[j] (1<=i<=m, i<=j<=n, i-1<=t

初始條件：b[t][0]=0(0<=t<=m)，b[0][t]=0(1<=t<=n)

max{b(m,j)}(m<=j<=n)即為n個整數(shù)序列的最大m子段和問題最終解。

算法基本思想為按上述狀態(tài)轉移方程構造一個m+1行(假設第0～m行)，n+1列(設第0～n列)的二維數(shù)組b，則第m行的最大元素為問題最終解。但實際設計算法時不必構造二維數(shù)組，因為只有第m行的最大元素為問題最終解，因此不必保存中間結果，經(jīng)優(yōu)化后得到如下經(jīng)典算法：

int MaxSum(int m,int n,int *a) {

int i,max,j,sum;

if(n

int *b=new int[n+1]; int *c=new int[n+1];

b[0]=0;

for(i=1;i<=m;i++) {

b[i]=b[i-1]+a[i]; c[i-1]=b[i]; max=b[i];

for(j=i+1;j<=i+n-m;j++) {

b[j]=b[j-1]>c[j-1]?b[j-1]+a[j]:c[j-1]+a[j];

c[j-1]=max;

if(max

}

c[i+n-m]=max;

}

sum=0;

for(j=m;j<=n;j++)

if(sum

return sum;

}

算法1 動態(tài)規(guī)劃常規(guī)算法

一、常規(guī)算法分析

下面對常規(guī)算法進行分析，計算過程如圖1所示：

圖1 常規(guī)算法計算過程

算法中需要兩個長度為n+1的輔助數(shù)組b和c，數(shù)組b用于保存第i行的數(shù)值，需要計算i+n-m個數(shù)值(因為最終解是最后一行的最大值，按狀態(tài)轉移方程，需要已知第m-1行第1～n-1列的數(shù)值，以此類推，如圖1斜線所示)；數(shù)組元素c[j]表示當前行從第一個元素到第j個元素的最大值，同樣也需要計算i+n-m個數(shù)值。

該算法雖然已經(jīng)過優(yōu)化，不必計算整個二維數(shù)組，只需保存一行數(shù)值以及該行從第一個數(shù)值到任一數(shù)值的最大值，而且不需要計算每一行的全部數(shù)值(如圖1)，但進一步分析發(fā)現(xiàn)，當計算第i行時，前面i-1個數(shù)值是無意義的，因為分成i段必須保證不少于i個數(shù)值，因此每一行需要計算的數(shù)值其實是一樣的，即n-m+1個。計算過程如圖2所示，圖中斜線部分即每一行需要計算的數(shù)值。

圖2 改進后的計算過程

另外，只需要設置一個中間變量表示當前行從第一個元素到第j個元素的最大值，而不必設置數(shù)組c。而且，在計算每一行數(shù)值時，可以在計算的過程中把每一行的最大值算出，不必在得出最后一行數(shù)據(jù)后再來查找最大值。

二、算法的改進

根據(jù)上述分析，對本算法進行改進：只需設置一個輔助數(shù)組b，維數(shù)是n-m+1，用于保存當前行n-m+1個數(shù)值，對應圖2的斜線部分數(shù)據(jù)，每計算新的一行，數(shù)組b中的元素都會被新的值替代；premax_to_i用于保存上一行第一個數(shù)字至第i個數(shù)字的最大值，curmax用于保存當前行的最大值。

改進后的算法如下：

int MaxSum(int m,int n,int *a) {

int i,index,premax_to_i,curmax;

if(n

int *b=new int[n-m+1];

for(i=0;i

for(index=1;index<=m;index++) {

premax_to_i=b[0];

b[0]=b[0]+a[index-1];

curmax=b[0];

for(i=1;i

if(b[i]>premax_to_i) premax_to_i=b[i];

b[i]=premax_to_i>b[i-1]?

premax_to_i+a[i+index-1]:b[i-1]+a[i+index-1];

if(b[i]>curmax) curmax=b[i];

}

}

delete[] b;

return curmax<0?0:curmax; //若最大值為負數(shù)，返回0

}

算法2 改進后的動態(tài)規(guī)劃算法

三、算法示例

假設有5個整數(shù){-2,2,3,8,-5}，現(xiàn)要找出3個不相交字段，使這3個子段的總和最大，利用上述改進的算法2，結果如下：

輸入： 輸出：

3 5 13

-2 2 3 8 -5

數(shù)組b的計算過程如下：

圖3 數(shù)組b的計算過程示例

因為在每次計算數(shù)組b時，同時得出每一行的最大值，而最后一行的最大值即為最終結果。

四、結 語

利用改進后的動態(tài)規(guī)劃算法，其時間復雜度雖然仍為O(m*(n-m))，但卻只用到一個中間數(shù)組，空間復雜度為O(n-m)，對于本算法的執(zhí)行效率還是有顯著改善的。

參考文獻：

[1]王曉東. 計算機算法設計與分析(第3版) [M]. 北京：電子工業(yè)出版社，2007.63～64.