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

三、求最大子段和

給定由n個(gè)整數(shù)（可能為負(fù)整數(shù)）組成的序列a1,a2,…,an,求該序列形如的子段和的最大值。當(dāng)所有整數(shù)均為負(fù)整數(shù)時(shí)定義其最大子段和為0。依此定義，所求的最優(yōu)值為：例如,當(dāng)（a1,a2,a3,a4,a5,a6)=（-2,11,-4,13,-5,-2）時(shí)，最大子段和為:=20。最大子段和問題的簡(jiǎn)單算法用數(shù)組a[]存儲(chǔ)給定的n個(gè)整數(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;}從這個(gè)算法的3個(gè)for循環(huán)可以看出它所需的計(jì)算時(shí)間是O(n3)事實(shí)上，如果我們注意到=則可將算法中的最后一個(gè)循環(huán)省去，避免重復(fù)計(jì)算，從而使算法得以改進(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ì)算時(shí)間。上述改進(jìn)是在算法設(shè)計(jì)技巧上的一個(gè)改進(jìn)，能充分利用已經(jīng)得到的結(jié)果，避免重復(fù)計(jì)算，節(jié)省了計(jì)算時(shí)間。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)這兩種情形可遞歸求得。對(duì)于情形(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）時(shí)，最大子段和為: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;}分治算法的時(shí)間復(fù)雜性分析時(shí)間復(fù)雜度：得T(n)=O(nlogn)

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

當(dāng)b[j-1]>0時(shí)，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

最大子段和問題的動(dòng)態(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）計(jì)算最優(yōu)值據(jù)此，可設(shè)計(jì)出求最大子段和的動(dòng)態(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;}