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

最大子段和问题*钱能武030130733讲课的主要内容:问题描述最大子段和问题的简单算法以及改进算法(枚举/穷举)最大子段和问题的分治算法最大子段和问题的动态规划算法推广1:最大子矩阵问题推广2:最大m字段和问题算法及改进算法补充内容:动态规划算法步骤1、找出最优解的性质,并刻画其结构特征2、递归地定义最优值3、以自底向上的方式计算最优值4、根据计算最优值时得到的信息结构最优解*最大子段和问题问题描述:给定由n个整数(可能为负整数)组成的序列a1,a2,…,an,求该序列形如ai,ai+1,…,aji,j=1,…,n,i≤j的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依此定义,所求的最优值为:例如:A=(-2,11,-4,13,-5,-2)11,-4,13最大子段和为:算法说明:1、算法中的thissum代表当前子段和,即a[i]到a[j]多有元素的和;sum代表函数结束时存储的最大子段和。besti代表最大子段和的起点下标,bestj代表代表最大子段和的终点下标。2、时间复杂度为O(n3).publicstaticintMaxSubsum(inta[]){intsum=0;intbesti;intbestj;for(inti=0;i<;i++){for(intj=i;j<;j++){intthissum=0;for(intk=i;k<=j;k++)thissum+=a[k];if(thissum>sum){sum=thissum;besti=i+1;bestj=j+1;}}}returnsum;}1、枚举算法设计*首先用最简单的枚举算法来解决这个问题。枚举所有可能的起始下标和终止下标,累加求和。并从中选取最大的字段和。*改进的枚举算法设计publicstaticintMaxSubsum(inta[]){intsum=0;intbesti;intbestj;for(inti=0;i<;i++){intthissum=0;for(intj=i;j<;j++){thissum+=a[j];if(thissum>sum){sum=thissum;besti=i+1;bestj=j+1;}}}returnsum;}thissum+=a[j];由知第k次计算的的和可由k-1次的结果递推。算法1每次都从头开始累加,则可将算法中的最内层一个for循环省去,避免重复计算。改进后的算法只需要O(n2)的计算时间2、分治算法经过以上改进只是减少了i一定时的重复计算操作。其中仍会有很多重复计算。从这个问题结构可以看出,它适合于用分治法求解。*如果将所给的序列a[1:n]分为长度相等的2段a[1:n/2]和a[n/2+1:n],分别求出这2段的最大子段和,则a[1:n]的最大子段和有3种情行。(1)a[1:n]的最大子段和与a[1:(n/2)]最大子段和相同;(2)a[1:n]的最大子段和与a[(n/2)+1:n]最大子段和相同;情形(1)、(2)可递归求得。(3)a[1:n]的最大子段和为,且1≤i≤n/2,(n/2)+1≤j≤n。*对于情形(3)。容易看出,序列元素a[(n/2)]与a[(n/2)+1]一定在最优子序列中。因此,可以计算出a[i:(n/2)]的最大值s1;并计算出a[(n/2)+1:j]中的最大值s2。则s1+s2即为出现情形(3)时的最优值。据此可设计出求最大子段和的分治算法。复杂度分析T(n)=O(nlogn)s1=0;//处理情形(3)  lefts=0;  for(i=center;i>=1;i--)  { lefts+=a[i];   if(lefts>s1)s1=lefts;}  s2=0;  rights=0;  for(j=center+1;j<=n;j++)  {   rights+=a[j];   if(rights>s2)    s2=rights;  }  sum=s1+s2;  if(sum<leftsum)   sum=leftsum;  if(sum<rightsum)   sum=rightsum; } returnsum;}*/*算法如下:intmaxsum(inta[],intleft,intright){intsum=0,leftsum,rightsum; inti,j; intlefts,rights; ints1,s2; intcenter; if(1==n) {  if(a[1]>0)   sum=a[1];  elsesum=0; } else {  center=(1+n)/2;  leftsum=maxsum(a,1,center);