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

最大子段和問題1講課的主要內(nèi)容：問題描述最大子段和問題的簡單算法以及改進(jìn)算法(枚舉/窮舉)最大子段和問題的分治算法最大子段和問題的動(dòng)態(tài)規(guī)劃算法推廣1：最大子矩陣問題推廣2：最大m字段和問題算法及改進(jìn)算法3最大子段和問題問題描述：給定由n個(gè)整數(shù)(可能為負(fù)整數(shù))組成的序列a1,a2,…,an,求該序列形如ai,ai+1,…,aji,j=1,…,n,i≤j的子段和的最大值。當(dāng)所有整數(shù)均為負(fù)整數(shù)時(shí)定義其最大子段和為０。依此定義，所求的最優(yōu)值為:例如:A=(-2，11，-4，13，-5，-2)11，-4，13最大子段和為：算法說明：1、算法中的thissum代表當(dāng)前子段和，即a[i]到a[j]元素的和；sum代表函數(shù)結(jié)束時(shí)存儲(chǔ)的最大子段和。besti代表最大子段和的起點(diǎn)下標(biāo)，bestj代表代表最大子段和的終點(diǎn)下標(biāo)。2、時(shí)間復(fù)雜度為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、枚舉算法設(shè)計(jì)4首先用最簡單的枚舉算法來解決這個(gè)問題。枚舉所有可能的起始下標(biāo)和終止下標(biāo)，累加求和。并從中選取最大的字段和。5改進(jìn)的枚舉算法設(shè)計(jì)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次計(jì)算的的和可由k-1次的結(jié)果遞推。算法1每次都從頭開始累加，則可將算法中的最后一個(gè)for循環(huán)省去，避免重復(fù)計(jì)算。改進(jìn)后的算法只需要O(n2)的計(jì)算時(shí)間2、分治算法

經(jīng)過以上改進(jìn)只是減少了i一定的重復(fù)計(jì)算操作,其中仍會(huì)有很多重復(fù)計(jì)算。從這個(gè)問題結(jié)構(gòu)可以看出，它適合于用分治法求解。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)可遞歸求得。

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

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

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;

}

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

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

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

0-2-70

92-62

-41-41

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

92例子2：

13-4

-2-56

179

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

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

因此在考慮第j個(gè)元素時(shí)，可能存在兩種情況：1）第j個(gè)元素和前一個(gè)元素一起包含在第i段中；2）第j個(gè)元素獨(dú)自劃分在第i段中。根據(jù)問題的分析，兩種情況分別如下：1）b(i,j-1)表示第j-1個(gè)元素的最大j子段和,所以b(i,j)=b(i,j-1)+a[j].2）max{b(i-1,k)}其中k=i-1..j-1.即表示為在第j個(gè)元素之前得到的i-1個(gè)子段之和的最優(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.①當(dāng)m=1時(shí)， 則該問題變?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因?yàn)閎(i,j)表示前j個(gè)元素的最大i子段和，并且必定包含第j個(gè)元素，這顯然不一定是最優(yōu)的。因此設(shè)g(i,j)表示前j個(gè)元素最大i子段和，其不一定包含第j個(gè)元素。由此我們可知：g(i,j)=max{g(i,j-1),b(i,j)}.

即得到表格如右圖所示：所以g[n][m]就是最大n子段和。0120123456i段第j元素0000-200119077020200151501318其實(shí)很簡單，我們最后來一個(gè)遍歷算法（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;所以接下來我們會(huì)產(chǎn)生一個(gè)問題：在算法中我們?cè)鯓油ㄟ^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;}參考代