最大子段和問題的動態(tài)規(guī)劃算法

三、求最大子段和

給定由n個整數(shù)（可能為負(fù)整數(shù)）組成的序列a1,a2,…,an,求該序列形如的子段和的最大值。當(dāng)所有整數(shù)均為負(fù)整數(shù)時定義其最大子段和為0。依此定義，所求的最優(yōu)值為：例如,當(dāng)（a1,a2,a3,a4,a5,a6)=（-2,11,-4,13,-5,-2）時，最大子段和為:=20。最大子段和問題的簡單算法用數(shù)組a[]存儲給定的n個整數(shù)a1,a2,…,an。intMaxSum（intn,inta*,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;}從這個算法的3個for循環(huán)可以看出它所需的計算時間是O(n3)事實上，如果我們注意到=則可將算法中的最后一個循環(huán)省去，避免重復(fù)計算，從而使算法得以改進(jìn)。改進(jìn)后的算法可描述為：intMaxSum（intn,int*a,int&besti,int&bestj）{intsum=0;

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

for(intj=i;j<=n;j++) {thissum+=a[j]; if(thissum>sum){sum=thissum;besti=i;bestj=j;}}}returnsum;}改進(jìn)后的算法只需要O(n2)的計算時間。上述改進(jìn)是在算法設(shè)計技巧上的一個改進(jìn)，能充分利用已經(jīng)得到的結(jié)果，避免重復(fù)計算，節(jié)省了計算時間。2.最大子段和問題的分治算法

從最大子段和問題的解的結(jié)構(gòu)可以看出，它適合用分治法求解。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。其中(1)和(2)這兩種情形可遞歸求得。對于情形(3),a[n/2]與a[n/2+1]在最優(yōu)子序列中，a[1:n]的最大子段和是a[1:n/2]的最大子段和與a[n/2+1：n]的最大子段和的和。

例如,當(dāng)（a1,a2,a3,a4,a5,a6)=（-2,11,-4,13,-5,-2）時，最大子段和為:Max{11,13,20}求最大子段和的分治算法如下：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;intlefts=0;

for

(inti=center;i>=left;i--){lefts+=a[i];if(lefts>s1)s1=lefts;}

ints2=0;intrights=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;}分治算法的時間復(fù)雜性分析時間復(fù)雜度：得T(n)=O(nlogn)

3.最大子段和問題的動態(tài)規(guī)劃算法（1）分析問題最優(yōu)解的結(jié)構(gòu)在對上述分治算法的分析中我們注意到，若記b[j]=,1≤j≤n,則所求最大子段和為：由b[j]的定義易知，

當(dāng)b[j-1]>0時，b[j]=b[j-1]+a[j]，

否則，b[j]=a[j]。（2）建立遞歸方程b[j]=max{b[j-1]+a[j],a[j]},1≤j≤n

最大子段和問題的動態(tài)規(guī)劃算法----例：a[n+1]11-2-2-4-5130154326b[n+1]0015432601ij0sumbestibestj00jjjjjjjjjjjj-2121121122374201320245156求a=（-2，11，-4，13，-5，-2）的最大子段和。a[n+1]11-2-2-4-5130154326b[n+1]00154326jjjjjjjjjjjj-2117201315（3）計算最優(yōu)值據(jù)此，可設(shè)計出求最大子段和的動態(tài)規(guī)劃算法如下：intMaxSum（intn,int*a）{intsum=0,b=0,i=0,besti=0,bestj=0;

for(intj=1;j<=n;j++) {if(b>0)b+=a[j]; else{b=a[j];i=j;}if(b>sum){sum=b;besti=i;bestj=j;}