廖作斌

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

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

最大m子段和的經典動態(tài)規(guī)劃優(yōu)化方法是：設b(i, j)表示前i個數劃分成j段，且包括第i個數的最大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個整數序列的最大m子段和問題最終解。

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

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

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

圖2 改進后的計算過程

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

二、算法的改進

根據上述分析，對本算法進行改進：只需設置一個輔助數組b，維數是n-m+1，用于保存當前行n-m+1個數值，對應圖2的斜線部分數據，每計算新的一行，數組b中的元素都會被新的值替代；premax_to_i用于保存上一行第一個數字至第i個數字的最大值，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; //若最大值為負數，返回0

}

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

三、算法示例

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

輸入： 輸出：

3 5 13

-2 2 3 8 -5

數組b的計算過程如下：

圖3 數組b的計算過程示例

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

四、結 語

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

參考文獻：

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