最大字段问题-含最大子矩阵和m子段和

最大子段和问题1讲课的主要内容：问题描述最大子段和问题的简单算法以及改进算法(枚举/穷举)最大子段和问题的分治算法最大子段和问题的动态规划算法推广1：最大子矩阵问题推广2：最大m字段和问题算法及改进算法3最大子段和问题问题描述：给定由n个整数(可能为负整数)组成的序列a1,a2,…,an,求该序列形如ai,ai+1,…,aji,j=1,…,n,i≤j的子段和的最大值。当所有整数均为负整数时定义其最大子段和为０。依此定义，所求的最优值为:例如: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循环省去，避免重复计算。改进后的算法只需要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]一定在最优子序列中。因此，可以计算出a[1:(n/2)]的最大值s1=

；并计算出a[(n/2)+1:n]中的最大值s2=。则s1＋s2即为出现情形(3)时的最优值。据此可设计出求最大子段和的分治算法。

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、动态规划算法

分治法减少了各分组之间的一些重复计算，但由于分解后的问题不独立，在情形（3）中重复计算较多，还是没有充分运用前期的计算结果。动态规划的特点就是解决分解的子问题不独立的情况。10动态规划的思路就是通过开辟存储空间，存储各子问题的计算结果，从而避免重复计算。其实就是用空间效率去换取时间效率。动态规划有很强的阶段递推思想，用前一段存储的计算结果，递推后一阶段的结果，是一种全面继承前期信息的方法。补充内容：动态规划算法步骤1、找出最优解的性质，并刻画其结构特征2、递归地定义最优值3、以自底向上的方式计算最优值4、根据计算最优值时得到的信息,构造最优解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]的动态规划递归式b[j]=max{b[j-1]+a[j]，a[j]}，1jn。算法设计：13动态规划法的时间复杂度为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的一个子矩阵，使其各元素之和为最大。即最大子矩阵和问题的最优值为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。

动态规划法：17动态规划法其实就是把二维最大子段和转化为一维最大子段和问题。转化方法：我们把这个矩阵划分成n个“条”，条的长度为1到m，通过两个for遍历所有长度的条。然后，若干个连续的条，就是一个子矩阵了，这样问题就轻易地转化为一维最大子段和问题了。通过求所有这种条，起点为i，长度为1到m-i+1的“条”的最大子段和，就可以求出整个矩阵的最大子矩阵了。18具体枚举长条的时候，同一起点的长度，由于“条”的不同长度间可以利用之前的结果。比如令b[k][i][j]表示第k个长“条”区间从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循环需要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)不一定是最优最大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个子段之和的最优选择。所以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时， 则该问题变为求最大字段和的问题例：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个元素，这显然不一定是最优的。因此设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循环），遍历所有的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;}参考代