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

1、最大子段和问题最大子段和问题 1钱能武钱能武030130733讲课的主要内容：讲课的主要内容： 问题描述问题描述 最大子段和问题的简单算法以及改进算法最大子段和问题的简单算法以及改进算法(枚举枚举/穷举穷举) 最大子段和问题的分治算法最大子段和问题的分治算法 最大子段和问题的动态规划算法最大子段和问题的动态规划算法 推广推广1：最大子矩阵问题：最大子矩阵问题 推广推广2：最大：最大m字段和问题算法及改进算法字段和问题算法及改进算法补充内容：补充内容：动态规划算法步骤动态规划算法步骤1、找出最优解的性质，并刻画其结构特征、找出最优解的性质，并刻画其结构特征2、递归地定义最优值、递归地定义最优值3

2、、以自底向上的方式计算最优值、以自底向上的方式计算最优值4、根据计算最优值时得到的信息结构最优解、根据计算最优值时得到的信息结构最优解3问题描述：给定由问题描述：给定由n个整数个整数(可能为负整数可能为负整数)组成的序列组成的序列a1,a2,an,求该序列形如求该序列形如 ai,ai+1,aj i,j=1, ,n,ij 的子段和的最大值。当所有整数均为负整数时定义其最大子段的子段和的最大值。当所有整数均为负整数时定义其最大子段和为。依此定义，所求的最优值为和为。依此定义，所求的最优值为:jikknjia1max, 0max例如例如: A=(-2，11，-4，13，-5，-2)11，-4，132

3、042kka最大子段和为：最大子段和为：算法说明：算法说明：1、算法中的算法中的thissum代表代表当前子段和，即当前子段和，即ai到到aj多多有元素的和；有元素的和；sum代表函数代表函数结束时存储的最大子段和。结束时存储的最大子段和。besti代表最大子段和的起代表最大子段和的起点下标，点下标，bestj代表代表最代表代表最大子段和的终点下标。大子段和的终点下标。2、时间复杂度为、时间复杂度为O(n3).public static int MaxSubsum(int a)int sum = 0;int besti;int bestj; for (int i=0;ia.length;i+)

4、 for (int j=i;ja.length;j+) int thissum=0; for (int k=i;ksum) sum=thissum; besti=i+1; bestj=j+1; return sum;4首先用最简单的枚举算法来解决这个问题。枚举所有可能的首先用最简单的枚举算法来解决这个问题。枚举所有可能的起始下标和终止下标，累加求和。并从中选取最大的字段和。起始下标和终止下标，累加求和。并从中选取最大的字段和。5public static int MaxSubsum(int a)int sum = 0;int besti;int bestj; for (int i=0;ia.l

5、ength;i+) int thissum=0; for (int j=i;jsum) sum=thissum; besti=i+1; bestj=j+1; return sum; thissum+=aj; 由由 知第知第k次计算次计算的的和可由的的和可由k-1次的结果次的结果递推。递推。 算法算法1每次都从每次都从头开始累加，则可将算头开始累加，则可将算法中的最内层一个法中的最内层一个for循循环省去，避免重复计算环省去，避免重复计算。1jikkjikjkaaa改进后的算法只需要改进后的算法只需要O(n2)的计算时间的计算时间 经过以上改进只是减少了经过以上改进只是减少了i一定时的重复计算操

6、一定时的重复计算操作。其中仍会有很多重复计算。从这个问题结构可以作。其中仍会有很多重复计算。从这个问题结构可以看出，它适合于用分治法求解。看出，它适合于用分治法求解。6 如果将所给的序列如果将所给的序列a1:n分为长度相等的分为长度相等的2段段a1:n/2和和an/2+1:n，分别求出这，分别求出这2段的最大子段和，段的最大子段和，则则a1:n的最大子段和有的最大子段和有3种情行。种情行。(1)a1:n的最大子段和与的最大子段和与a1:(n/2)最大子最大子段和相同；段和相同；(2)a1:n的最大子段和与的最大子段和与a(n/2)+1:n最大最大子段和相同；子段和相同； 情形情形(1)、(2)

7、可递归求得。可递归求得。(3)a1:n的最大子段和为的最大子段和为 ,且且1in/2,(n/2)+1jn。7 对于情形对于情形(3)。容易看出，序列元素。容易看出，序列元素a(n/2)与与a(n/2)+1一定在最优子序列中。因此，可以计算出一定在最优子序列中。因此，可以计算出ai:(n/2)的最大值的最大值s1；并计算出；并计算出a(n/2)+1:j中的最大值中的最大值s2。则。则s1s2即为出现情形即为出现情形(3)时的最优值。据此可设计时的最优值。据此可设计出求最大子段和的分治算法出求最大子段和的分治算法。复杂度分析复杂度分析T(n)=O(nlogn) s1 = 0; /处理情形处理情形(

8、3) lefts = 0; for (i = center; i = 1; i-) lefts += ai; if (lefts s1) s1 = lefts; s2 = 0; rights = 0; for (j = center + 1; j s2) s2 = rights; sum = s1 + s2; if (sum leftsum) sum = leftsum; if (sum 0) sum = a1; else sum = 0; else center = (1 + n) / 2; leftsum = maxsum(a,1, center); rightsum = maxsum(a

9、,center + 1, n); 3、动态规划算法、动态规划算法 分治法减少了各分组之间的一些重复计算，但由于分解后的问题分治法减少了各分组之间的一些重复计算，但由于分解后的问题不独立，在情形（不独立，在情形（3）中重复计算较多，还是没有充分运用前期的计）中重复计算较多，还是没有充分运用前期的计算结果。动态规划的算结果。动态规划的特长特长就是解决分解的子问题不独立的情况。就是解决分解的子问题不独立的情况。9动态规划的思路就是通过开辟存储空间，存储各子问题的计算结动态规划的思路就是通过开辟存储空间，存储各子问题的计算结果，从而避免重复计算。果，从而避免重复计算。其实就是用空间效率去换取时间效率。

10、其实就是用空间效率去换取时间效率。动态规划有很强的动态规划有很强的阶段递推思想阶段递推思想，用前一段存储的计算结果，递用前一段存储的计算结果，递推后一阶段的结果，是一种全面继承前期信息的方法。推后一阶段的结果，是一种全面继承前期信息的方法。10记记 sum为为a1 aj的最大子段和，记的最大子段和，记bj为当前子段和。为当前子段和。 即即 ，1 j n。当当bj-10时，前面子段的和对总和有贡献，所以要累加前时，前面子段的和对总和有贡献，所以要累加前面的值。面的值。bj=bj-1+aj，当，当bj-1 0时，前面子段的和对总时，前面子段的和对总和没有贡献，要重新累加，和没有贡献，要重新累加，

11、bj =aj。由此可得计算。由此可得计算bj的动的动态规划递归式态规划递归式bj=maxbj-1+aj，aj， 1 j n。 max1jikjikajb算法设计：算法设计：举例举例：11k12345ak3-42101bk3-121213其中：其中：b1=a1=3，b2=b1+a2=-1，b3=a3=2，b4=b3+a4 =12,b5=b4+a5 =13；因此，对于数组因此，对于数组a 而言，最大子段和为而言，最大子段和为b5，即即sum=13。12动态规划法的计算时间复杂度为动态规划法的计算时间复杂度为O(n)程序实现程序实现：public static int MaxSubsum(int a

12、,int n)int sum = 0,b = 0;for(int i=0;i0) b+=ai; else b = ai; if(bsum) sum = b; return sum;这已经是一个简化后的算法，最基本的这已经是一个简化后的算法，最基本的做法其实可以申请一个做法其实可以申请一个bn数组，每次数组，每次求解求解bj=maxbj-1+aj，aj ，最后，最后遍历遍历bn求得最大数组即可。求得最大数组即可。子段和问题的扩展子段和问题的扩展2维最大子段和维最大子段和13 二维最大子段和问题又称为最大子矩阵问题二维最大子段和问题又称为最大子矩阵问题,给定一给定一个个m行行n列的整数矩阵列的整数

13、矩阵a，试求矩阵，试求矩阵a的一个子矩阵，使的一个子矩阵，使其各元素之和为最大。其各元素之和为最大。 即即 最大子矩阵和问题的最优值为最大子矩阵和问题的最优值为2121)2, 1, 2, 1(iiijjjjiajjiis)2, 1, 2, 1(max211211jjiisnjjmii14如图所示，在二维最大子段和问题中，我们要求的是这如图所示，在二维最大子段和问题中，我们要求的是这样一个子矩阵，如图中红框所示，其中样一个子矩阵，如图中红框所示，其中 0 i j m-1 , 0 p q n-1。例子1： 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 其最大子矩阵为：9 2其元素总和为

14、11。 9 2例子2： 1 3 -4 -2 -5 6 1 7 9 -5 6 7 9其最大子矩阵为：-5 67 9其元素总和为17。 动态规划法：动态规划法：16动态规划法其实就是动态规划法其实就是把二维最大子段和转化为把二维最大子段和转化为一维最大子段和问题。一维最大子段和问题。转化方法：转化方法：我们把这个矩阵划分成我们把这个矩阵划分成n个个“条条”，条的长度为，条的长度为1到到m，通过两个，通过两个for遍历所有长度的条。遍历所有长度的条。然后，若干个连续的条，就是一个子矩阵了，这样然后，若干个连续的条，就是一个子矩阵了，这样问题就轻易地转化为一维最大子段和问题了。问题就轻易地转化为一维最

15、大子段和问题了。通过求所有这种条，起点为通过求所有这种条，起点为i，长度为，长度为1到到m-i+1的的“条条”的最大子段和，就可以求出整个矩阵的最大的最大子段和，就可以求出整个矩阵的最大子矩阵了。子矩阵了。17具体枚举长条的时候，同一起点的长度，由于具体枚举长条的时候，同一起点的长度，由于“条条”的不的不同长度间可以利用之前的结果。同长度间可以利用之前的结果。比如令比如令bkij表示第表示第k个长个长“条条”区间从区间从i到到j的和，那么的和，那么bkij+1 = bkij+ajk。当然，实际编程的时候，由于之前的结果求完一维最大子当然，实际编程的时候，由于之前的结果求完一维最大子段和后，便不

16、需要保存，所以只需要段和后，便不需要保存，所以只需要一维数组一维数组b即可。即可。参考代码参考代码18public 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(m2n)的

17、计算时间的计算时间特别的：特别的：当当m= O(n)时算法需时算法需要要O(n3)计算时间计算时间 最大最大m子段和问题：给定由子段和问题：给定由n个整数（可能为负）组个整数（可能为负）组成的序列成的序列a1、a2、a3.,an,以及一个正整数以及一个正整数m，要求确定，要求确定序列的序列的m个不相交子段，使这个不相交子段，使这m个子段的总和最大！个子段的总和最大！ 例如：序列为例如：序列为 2 3 -7 6 4 -5 若要求的若要求的m=3子段和问题的扩展子段和问题的扩展最大最大m字段和字段和其中其中3个字段应该是个字段应该是 2、3 6 4和为：和为：15当当m1时时 设设b(i,j)表示

18、前表示前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子段和子段和,

19、所以所以b(i,j)=b(i,j-1)+aj. 2）maxb(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时，时，则该问题变为求最大字段和的问题则该问题变为求最大字段和的问题例：例： a ：000002000500506010010i段段 0 1 2 3 0 1 2 3 4 5 6b(i,

20、j)=maxb(i,j-1)+aj,max b(i-1,k)+aj,其中其中k=i-1.j-1.a1a2a3a4a5a623-764-5第第 元元素素j5-2-2111115151010 因为因为b(i,j)表示前表示前j个元素的最个元素的最大大i子段和，并且必定包含第子段和，并且必定包含第j个元个元素，这显然素，这显然不一定是最优的不一定是最优的。因此。因此设设g(i,j)表示前表示前j个元素最大个元素最大i子段和，子段和，其不一定包含第其不一定包含第j个元素。个元素。 由此我们可知：由此我们可知： g(i,j)=maxg(i,j-1),b(i,j). 即得到表格如右图所示：即得到表格如右图

21、所示： 所以所以gnm就是最大就是最大n子段子段和。和。000002000550055-206111101015150101515 0 1 2 3 0 1 2 3 4 5 6i段段第第j元素元素b(i,j)=maxb(i,j-1)+aj,b(i-1,k)+aj,其中其中k=i-1.j-1.g(i,j)=maxg(i,j-1),b(i,j).bij表：表：gij表：表：00000200050050601001055-2111115151515 其实很简单，我们最后来一个遍历算法（其实很简单，我们最后来一个遍历算法（for循环），循环），遍历所有的遍历所有的bmmn取得其中的最大值就行了。取得其中

22、的最大值就行了。代码：代码：int sum = 0;for(int j = m;j = n;j+)if(sum bmj) sum = bmj;return sum;所以接下来我们会产生一个所以接下来我们会产生一个问题：问题： 在算法中我们怎样通过在算法中我们怎样通过bij去求得我们的最大去求得我们的最大m字段和？字段和？public static 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;