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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,最大子段和问题,1,1,讲课的主要内容：,问题描述,最大子段和问题的简单算法以及改进算法(枚举/穷举),最大子段和问题的分治算法,最大子段和问题的动态规划算法,推广1：最大子矩阵问题,推广2：最大m字段和问题算法及改进算法,2,3,最大子段和问题,问题描述：给定由,n,个整数,(,可能为负整数,),组成的序列,a,1,a,2,a,n,求该序列形如,a,i,a,i+1,a,j,i,j=1,n,i,j,的子段和的最大值。当所有整数均为负整数时定义其最大子段,和为。依此定义，所求的最优值为:,例如:,A=(-2,，,11,，,-4,，,13,，,-5,，,-2),最大子段和为：,3,算法说明：,1,、,算法中的,thissum,代表当前子段和，即,ai,到,aj,元素的和；,sum,代表函数结束时存储的最大子段和。,besti,代表最大子段和的起点下标，,bestj,代表代表最大子段和的终点下标。,2,、时间复杂度为,O(n,3,).,int MaxSum(int n,int*a,int&besti,int&bestj),int sum=0;,for(int i=1;i=n;i+),for(int j=i;j=n;j+),int thissum=0;,for(int k=i;ksum),sum=thissum;,besti=i;,bestj=j;,return sum;,1、枚举算法设计,4,首先用最简单的枚举算法来解决这个问题。枚举所有可能的,起始下标和终止下标，累加求和。并从中选取最大的字段和。,4,5,改进的枚举算法设计,int,MaxSubsum(,int,n,int,*a,int,&besti,int,&bestj),int,sum=0;,for,(,int,i=,1,;,i=n,;i+),int,thissum=0;,for,(,int,j=i;jsum),sum=thissum;,besti=i;,bestj=j;,return,sum;,thissum+=aj;,由 知第,k,次计算的的和可由,k-1,次的结果递推。算法,1,每次都从头开始累加，则可将算法中的最后一个,for,循环省去，避免重复计算,。,改进后的算法只需要,O(n,2,),的计算时间,5,2、分治算法,经过以上改进只是减少了i一定的重复计算操作,其中仍会有很多重复计算。从这个问题结构可以看出，它适合于用分治法求解。,6,如果将所给的序列,a1:n,分为长度相等的两段,a1:n/2,和,an/2+1:n,，分别求出这两段的最大子段和，则,a1:n,的最大子段和有三种情形：,(1)a1:n,的最大子段和与,a1:(n/2),最大子段和相同；,(2)a1:n,的最大子段和与,a(n/2)+1:n,最大子段和相同；,(3)a1:n,的最大子段和为,且,1in/2,(n/2)+1jn,。,6,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),时的最优值。据此可设计出求最大子段和的分治算法。,7,int s2=0;intrights=0;for(int i=center+1;i s2)s2=rights;,sum=s1+s2;if(sum leftsum)sum=leftsum;if(sum 0?aleft:0;,else,int,center=(,left+right,)/2;,int,leftsum=,M,ax,SubS,um(a,left,center);,int,rightsum=,M,ax,SubS,um(a,center+1,right,);,int s1=0;/处理情形(3),int lefts=0;,for(int i=center;i=left;i-),lefts+=ai;,if(lefts s1)s1=lefts;,8,复杂度分析,满足典型的分治算法递归式,解此递归方程，得T(n)=,O(nlogn),9,3、动态规划算法,分治法减少了各分组之间的一些重复计算，但由于分解后的问题不独立，在情形（3）中重复计算较多，还是没有充分运用前期的计算结果。动态规划的,特点,就是解决分解的子问题不独立的情况。,10,动态规划的思路就是通过开辟存储空间，存储各子问题的计算结果，从而避免重复计算。,其实就是用空间效率去换取时间效率。,动态规划有很强的,阶段递推思想,，,用前一段存储的计算结果，递推后一阶段的结果，是一种全面继承前期信息的方法。,10,补充内容：,动态规划算法步骤,1,、找出最优解的性质，并刻画其结构特征,2,、递归地定义最优值,3,、以自底向上的方式计算最优值,4,、根据计算最优值时得到的信息,构造最优解,11,12,记,sum,为,a1 aj,的最大子段和，记,bj,为当前子段和。,即 ，,1,j,n,。,当,bj-10,时，前面子段的和对总和有贡献，所以要累加前面的值，,bj=bj-1+aj,；,当,bj-1,0,时，前面子段的和对总和没有贡献，要重新累加，,bj=aj,。,由此可得计算,bj,的动态规划递归式,bj=maxbj-1+aj,，,aj,，,1,j,n,。,算法设计：,12,13,动态规划法的,时间复杂度为,O(n),，,空间复杂度为,O(n),程序实现,：,int,MaxSum(,int,n,int,*a,),int,sum=0,b=0;,for,(,int,i=,1,;i0),b+=ai;,else,b=ai;,if,(bsum),sum=b;,return,sum;,13,子段和问题的扩展2维最大子段和,14,二维最大子段和问题又称为最大子矩阵问题,给定一个,m,行,n,列的整数矩阵,a,，试求矩阵,a,的一个子矩阵，使其各元素之和为最大。,即,最大子矩阵和问题的最优值为,14,15,如图所示，在二维最大子段和问题中，我们要求的是这样一个子矩阵，如图中红框所示，其中,0,i,j,m-1,0,p,q,n-1,。,15,例子,1,：,0 -2 -7 0 9 2 -6 2 -4 1 -4 1,其最大子矩阵为：,9 2,其元素总和为,11,。,例子,2,：,1 3 -4 -2 -5 6 1 7 9,其最大子矩阵为：,-5 6,7 9,其元素总和为,17,。,16,动态规划法：,17,动态规划法其实就是,把二维最大子段和转化为一维最大子段和问题。,转化方法：,我们把这个矩阵划分成,n,个“条”，条的长度为,1,到,m,，通过两个,for,遍历所有长度的条。,然后，若干个连续的条，就是一个子矩阵了，这样问题就轻易地转化为一维最大子段和问题了。,通过求所有这种条，起点为,i,，长度为,1,到,m-i+1,的“条”的最大子段和，就可以求出整个矩阵的最大子矩阵了。,17,18,具体枚举长条的时候，同一起点的长度，由于“条”的不同长度间可以利用之前的结果。,比如令,bkij,表示第,k,个长“条”区间从,i,到,j,的和，那么,bkij+1=bkij+ajk,。,当然，实际编程的时候，由于之前的结果求完一维最大子段和后，便不需要保存，所以只需要,一维数组,b,即可。,18,参考代码,19,public static int MaxSum(int a,int m,int n),int sum=0;,int b=new intn;,for(int i=0;i m;i+),for(int k=0;k n;k+)bk=0;,for(int j=i;j m;j+),for(int k=0;k sum)sum=max;,return sum;,由于,MaxSubsum,(),需要,O(n),的时间，估此算法的双重,for,循环需要,O(m,2,n),的计算时间,特别的：,当,m=O(n),时算法需要,O(n,3,),计算时间,19,最大,m,子段和问题：给定由,n,个整数（可能为负）组成的序列,a1,、,a2,、,a3.,an,以及一个正整数,m,，要求确定序列的,m,个不相交子段，使这,m,个子段的总和最大！,例如：序列为 2 3-7 6 4-5 若要求的m=3,子段和问题的扩展最大m字段和,其中,3,个字段应该是,2,、,3 6 4,和为：,15,20,当m1时,设,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)+aj.,2）max,b(i-1,k),其中k=,i-1.j-1.,即表示为在第,j,个元素之前得到的,i-1,个子段之和的最优选择。所以,b(i,j)=maxb(i-1,k)+aj,其中k=,i-1.j-1.,综上：,b(i,j)=maxb(i,j-1)+aj,max b(i-1,k),+aj,其中k=,i-1.j-1.,当m=1时，,则该问题变为求最大字段和的问题,21,例：,a：,i,段,0 1 2,0,1,2,3,4,5,6,b(i,j)=maxb(i,j-1)+aj,max b(i-1,k)+aj,其中k=,i-1.j-1.,第,元素,j,22,因为,b(i,j),表示前,j,个元素的最大,i,子段和，并且必定包含第,j,个元素，这显然,不一定是最优的,。因此设g(i,j)表示前,j,个元素最大,i,子段和，其不一定包含第,j,个元素。,由此我们可知：,g(i,j)=maxg(,i,j-1),b(i,j).,即得到表格如右图所示：,所以gnm就是最大,n,子段和。,0 1 2,0,1,2,3,4,5,6,i,段,第,j,元素,23,其实很简单，我们最后来一个遍历算法（,for,循环），遍历所有的,bmmn,取得其中的最大值就行了。,代码：,int,sum=0;,for,(,int,j=m;j=n;j+),if,(sum bmj)sum=bmj;,return,sum;,所以接下来我们会产生一个,问题：,在算法中我们怎样通过,bij,去求得我们的最大,m,字段和？,24,int MaxSubsum(int m,int n,int a),if(n m|m1)return 0;,int b=new intm+1;,for(int i=0;i=m;i+)bi=new intn+1;,for(int i=0;i=m;i+)bi0=0;,for(int j=1;j=n;j+)b0j=0;,for(int i=1;i=m;i+),for(int j=i;j i),bij=bij-1+aj-1;,for(int k=i-1;k j;k+),if(bij bi-1k+aj-1)bij=bi-1k+aj-1;,else bij=bi-1j-1+aj-1;,int sum=0;,for(int j=m;j=n;j+),if(sum bmj)sum=bmj;,return sum;,参考代码：,复杂度分析：,算法需要,O(mn,2,),的计算时间和,O(mn),空间,25,算法改进：,注意到算法中计算bij时只用到了数组b的第i-1行和第i行的值，因此只要存储数组b的当前行，不必存储整个数组（节省空间开销）；另外，max b(i-1,t)（其中i-1=tj）的值可以再计算第i-1行时预先计算并保存起来，这样就不必重新计算，节省计算时间。,int MaxSum(int m,int n,int*a),if(nm|m1)return 0;,int*b=new intn+1;,int*c=new intn+1;,b0=0;,c1=0;,for(int i=1;i=m;i+),bi=bi-1+ai;,ci-1=bi;,int max=bi;,for(int j=i+1;jcj-1?bj-1+aj:cj-1+aj;,cj-1=max;,if(maxbj)max=bj;,ci+n-m=max;,int sum=0;,for(int j=m;j=n;j+),if(sumbj)sum=bj;,return sum;,26,谢谢！,27,