最大字段問題-含最大子矩陣和m子段和

最大子段和問題1講課的主要內容：問題描述最大子段和問題的簡單算法以及改進算法(枚舉/窮舉)最大子段和問題的分治算法最大子段和問題的動態(tài)規(guī)劃算法推廣1：最大子矩陣問題推廣2：最大m字段和問題算法及改進算法3最大子段和問題問題描述：給定由n個整數(可能為負整數)組成的序列a1,a2,…,an,求該序列形如ai,ai+1,…,aji,j=1,…,n,i≤j的子段和的最大值。當所有整數均為負整數時定義其最大子段和為０。依此定義，所求的最優(yōu)值為:例如:A=(-2，11，-4，13，-5，-2)11，-4，13最大子段和為：算法說明：1、算法中的thissum代表當前子段和，即a[i]到a[j]元素的和；sum代表函數結束時存儲的最大子段和。besti代表最大子段和的起點下標，bestj代表代表最大子段和的終點下標。2、時間復雜度為O(n3).intMaxSum(intn,int*a,int&besti,int&bestj){

intsum=0;for(inti=1;i<=n;i++){for(intj=i;j<=n;j++){

intthissum=0;for(intk=i;k<=j;k++)thissum+=a[k];if(thissum>sum){sum=thissum;besti=i;bestj=j;}}

}returnsum;}1、枚舉算法設計4首先用最簡單的枚舉算法來解決這個問題。枚舉所有可能的起始下標和終止下標，累加求和。并從中選取最大的字段和。5改進的枚舉算法設計intMaxSubsum(int

n,int*a,int&besti,int

&bestj){

intsum=0;

for(inti=1;i<=n;i++){

intthissum=0;

for(intj=i;j<=n;j++){

if(thissum>sum){

sum=thissum;

besti=i;

bestj=j;}}}returnsum;}thissum+=a[j];由知第k次計算的的和可由k-1次的結果遞推。算法1每次都從頭開始累加，則可將算法中的最后一個for循環(huán)省去，避免重復計算。改進后的算法只需要O(n2)的計算時間2、分治算法

經過以上改進只是減少了i一定的重復計算操作,其中仍會有很多重復計算。從這個問題結構可以看出，它適合于用分治法求解。6

如果將所給的序列a[1:n]分為長度相等的兩段a[1:n/2]和a[n/2+1:n]，分別求出這兩段的最大子段和，則a[1:n]的最大子段和有三種情形：(1)a[1:n]的最大子段和與a[1:(n/2)]最大子段和相同；(2)a[1:n]的最大子段和與a[(n/2)+1:n]最大子段和相同；(3)a[1:n]的最大子段和為,且1≤i≤n/2,(n/2)+1≤j≤n。7

情形(1)、(2)可遞歸求得。

對于情形(3)。容易看出，序列元素a[(n/2)]與a[(n/2)+1]一定在最優(yōu)子序列中。因此，可以計算出a[1:(n/2)]的最大值s1=

；并計算出a[(n/2)+1:n]中的最大值s2=。則s1＋s2即為出現情形(3)時的最優(yōu)值。據此可設計出求最大子段和的分治算法。

ints2=0;

int

rights=0;

for(inti=center+1;i<=right;i++)

{

rights+=a[i];

if(rights>s2)

s2=rights;

}

sum=s1+s2;

if(sum<leftsum)

sum=leftsum;

if(sum<rightsum)

sum=rightsum;

}

returnsum;

}intMaxSum(intn,int*a){returnMaxSubSum(a,1,n);}8算法如下：intMaxSubSum(int*a,intleft,intright){

intsum=0;

if(left==right)

sum=a[left]>0?a[left]:0;

else{

intcenter=(left+right)/2;

intleftsum=MaxSubSum(a,left,center);

intrightsum=MaxSubSum(a,center+1,right);

ints1=0;//處理情形(3)

intlefts=0;

for(inti=center;i>=left;i--)

{

lefts+=a[i];

if(lefts>s1)s1=lefts;

}

復雜度分析滿足典型的分治算法遞歸式解此遞歸方程，得T(n)=O(nlogn)3、動態(tài)規(guī)劃算法

分治法減少了各分組之間的一些重復計算，但由于分解后的問題不獨立，在情形（3）中重復計算較多，還是沒有充分運用前期的計算結果。動態(tài)規(guī)劃的特點就是解決分解的子問題不獨立的情況。10動態(tài)規(guī)劃的思路就是通過開辟存儲空間，存儲各子問題的計算結果，從而避免重復計算。其實就是用空間效率去換取時間效率。動態(tài)規(guī)劃有很強的階段遞推思想，用前一段存儲的計算結果，遞推后一階段的結果，是一種全面繼承前期信息的方法。補充內容：動態(tài)規(guī)劃算法步驟1、找出最優(yōu)解的性質，并刻畫其結構特征2、遞歸地定義最優(yōu)值3、以自底向上的方式計算最優(yōu)值4、根據計算最優(yōu)值時得到的信息,構造最優(yōu)解12記sum為a[1]~a[j]的最大子段和，記b[j]為當前子段和。即，1jn。當b[j-1]>0時，前面子段的和對總和有貢獻，所以要累加前面的值，b[j]=b[j-1]+a[j]；當b[j-1]0時，前面子段的和對總和沒有貢獻，要重新累加，b[j]=a[j]。由此可得計算b[j]的動態(tài)規(guī)劃遞歸式b[j]=max{b[j-1]+a[j]，a[j]}，1jn。算法設計：13動態(tài)規(guī)劃法的時間復雜度為O(n)，空間復雜度為O(n)程序實現：intMaxSum(intn,int*a){

intsum=0,b=0;

for(inti=1;i<=n;i++){

if(b>0)

b+=a[i];

elseb=a[i];

if(b>sum)

sum=b;

}returnsum;}子段和問題的擴展—2維最大子段和14

二維最大子段和問題又稱為最大子矩陣問題,給定一個m行n列的整數矩陣a，試求矩陣a的一個子矩陣，使其各元素之和為最大。即最大子矩陣和問題的最優(yōu)值為15如圖所示，在二維最大子段和問題中，我們要求的是這樣一個子矩陣，如圖中紅框所示，其中0ijm-1,0pqn-1。例子1：

0-2-70

92-62

-41-41

其最大子矩陣為：92其元素總和為11。

92例子2：

13-4

-2-56

179

-5679其最大子矩陣為：-5679其元素總和為17。

動態(tài)規(guī)劃法：17動態(tài)規(guī)劃法其實就是把二維最大子段和轉化為一維最大子段和問題。轉化方法：我們把這個矩陣劃分成n個“條”，條的長度為1到m，通過兩個for遍歷所有長度的條。然后，若干個連續(xù)的條，就是一個子矩陣了，這樣問題就輕易地轉化為一維最大子段和問題了。通過求所有這種條，起點為i，長度為1到m-i+1的“條”的最大子段和，就可以求出整個矩陣的最大子矩陣了。18具體枚舉長條的時候，同一起點的長度，由于“條”的不同長度間可以利用之前的結果。比如令b[k][i][j]表示第k個長“條”區(qū)間從i到j的和，那么b[k][i][j+1]=b[k][i][j]+a[j][k]。當然，實際編程的時候，由于之前的結果求完一維最大子段和后，便不需要保存，所以只需要一維數組b即可。參考代碼19publicstaticintMaxSum(inta[][],intm,intn){intsum=0;intb[]=newint[n];for(inti=0;i<m;i++){for(intk=0;k<n;k++)b[k]=0;for(intj=i;j<m;j++){for(intk=0;k<n;k++)b[k]+=a[j][k];intmax=MaxSubsum(b,n);if(max>sum)sum=max;}}returnsum;}由于MaxSubsum()需要O(n)的時間，估此算法的雙重for循環(huán)需要O(m2n)的計算時間特別的：當m=O(n)時算法需要O(n3)計算時間最大m子段和問題：給定由n個整數（可能為負）組成的序列a1、a2、a3...,an,以及一個正整數m，要求確定序列的m個不相交子段，使這m個子段的總和最大！例如：序列為23-764-5若要求的m=3子段和問題的擴展—最大m字段和其中3個字段應該是{2、3}{6}{4}和為：15②當m>1時設b(i,j)表示前j個元素(必定包含第j個元素)分為互不相交的i段所得的最大i子段和并且i<=j。(注：b(i,j)不一定是最優(yōu)最大i子段和)

因此在考慮第j個元素時，可能存在兩種情況：1）第j個元素和前一個元素一起包含在第i段中；2）第j個元素獨自劃分在第i段中。根據問題的分析，兩種情況分別如下：1）b(i,j-1)表示第j-1個元素的最大j子段和,所以b(i,j)=b(i,j-1)+a[j].2）max{b(i-1,k)}其中k=i-1..j-1.即表示為在第j個元素之前得到的i-1個子段之和的最優(yōu)選擇。所以b(i,j)=max{b(i-1,k)+a[j]},其中k=i-1..j-1.綜上：b(i,j)=max{b(i,j-1)+a[j],maxb(i-1,k)+a[j]},其中k=i-1..j-1.①當m=1時， 則該問題變?yōu)榍笞畲笞侄魏偷膯栴}例：a：0000-2001107020015013i段0120123456b(i,j)=max{b(i,j-1)+a[j],maxb(i-1,k)+a[j]},其中k=i-1..j-1.a[1]a[2]a[3]a[4]a[5]a[6]-211-413-5-2第

元素j97201518因為b(i,j)表示前j個元素的最大i子段和，并且必定包含第j個元素，這顯然不一定是最優(yōu)的。因此設g(i,j)表示前j個元素最大i子段和，其不一定包含第j個元素。由此我們可知：g(i,j)=max{g(i,j-1),b(i,j)}.

即得到表格如右圖所示：所以g[n][m]就是最大n子段和。0120123456i段第j元素0000-200119077020200151501318其實很簡單，我們最后來一個遍歷算法（for循環(huán)），遍歷所有的b[m][m……n]取得其中的最大值就行了。代碼：intsum=0;for(intj=m;j<=n;j++){ if(sum<b[m][j])sum=b[m][j]; }returnsum;所以接下來我們會產生一個問題：在算法中我們怎樣通過b[i][j]去求得我們的最大m字段和？intMaxSubsum(intm,intn,inta[]){if(n<m||m<1)return0;intb[][]=newint[m+1][];for(inti=0;i<=m;i++){b[i]=newint[n+1];}for(inti=0;i<=m;i++){b[i][0]=0;}for(intj=1;j<=n;j++){b[0][j]=0;}for(inti=1;i<=m;i++){for(intj=i;j<=n-m+i;j++){//n-m+i確保后面的元素可以夠分成m-i段if(j>i){b[i][j]=b[i][j-1]+a[j-1];for(intk=i-1;k<j;k++){if(b[i][j]<b[i-1][k]+a[j-1])b[i][j]=b[i-1][k]+a[j-1];}}elseb[i][j]=b[i-1][j-1]+a[j-1];}}intsum=0;for(intj=m;j<=n;j++){if(sum<b[m][j])sum=b[m][j];}returnsum;}參考代