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

1、最大子段和问题,1,钱能武 030130733,讲课的主要内容：,问题描述 最大子段和问题的简单算法以及改进算法(枚举/穷举) 最大子段和问题的分治算法 最大子段和问题的动态规划算法 推广1：最大子矩阵问题 推广2：最大m字段和问题算法及改进算法,补充内容：动态规划算法步骤 1、找出最优解的性质，并刻画其结构特征 2、递归地定义最优值 3、以自底向上的方式计算最优值 4、根据计算最优值时得到的信息结构最优解,3,最大子段和问题,问题描述：给定由n个整数(可能为负整数)组成的序列a1,a2,an,求该序列形如 ai,ai+1,aj i,j=1, ,n,ij 的子段和的最大值。当所有整数均为负整数

2、时定义其最大子段 和为。依此定义，所求的最优值为:,例如: A=(-2，11，-4，13，-5，-2),最大子段和为：,算法说明： 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;isum) sum=thissum; besti=i+1; bestj=j+1; ret

3、urn sum; ,1、枚举算法设计,4,首先用最简单的枚举算法来解决这个问题。枚举所有可能的 起始下标和终止下标，累加求和。并从中选取最大的字段和。,5,改进的枚举算法设计,public static int MaxSubsum(int a) int sum = 0; int besti; int bestj; for (int i=0;isum) sum=thissum; besti=i+1; bestj=j+1; return sum; ,thissum+=aj;,由 知第k次计算的的和可由k-1次的结果递推。 算法1每次都从头开始累加，则可将算法中的最内层一个for循环省去，避免重复计

4、算。,改进后的算法只需要O(n2)的计算时间,2、分治算法,经过以上改进只是减少了i一定时的重复计算操作。其中仍会有很多重复计算。从这个问题结构可以看出，它适合于用分治法求解。,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)可递归求得。 (3)a1:n的最大子段和为 , 且1in/2,(n/2)+1jn。,7,对于情形(3)。容易看出，序列元素a(n/2)

5、与a(n/2)+1一定在最优子序列中。因此，可以计算出ai:(n/2)的最大值s1；并计算出a(n/2)+1:j中的最大值s2。则s1s2即为出现情形(3)时的最优值。据此可设计出求最大子段和的分治算法。,复杂度分析 T(n)=O(nlogn),s1 = 0; /处理情形(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 lefts

6、um)sum = leftsum;if (sum rightsum)sum = rightsum;return sum;*/,8,算法如下： int maxsum(int a, int left, int right) int sum = 0,leftsum,rightsum;int i,j;int lefts,rights;int s1,s2;int center;if (1 = n)if (a1 0)sum = a1;else sum = 0;elsecenter = (1 + n) / 2;leftsum = maxsum(a,1, center);rightsum = maxsum(a

7、,center + 1, n);,3、动态规划算法,分治法减少了各分组之间的一些重复计算，但由于分解后的问题不独立，在情形（3）中重复计算较多，还是没有充分运用前期的计算结果。动态规划的特长就是解决分解的子问题不独立的情况。,9,动态规划的思路就是通过开辟存储空间，存储各子问题的计算结果，从而避免重复计算。其实就是用空间效率去换取时间效率。 动态规划有很强的阶段递推思想，用前一段存储的计算结果，递推后一阶段的结果，是一种全面继承前期信息的方法。,10,记 sum为a1 aj的最大子段和，记bj为当前子段和。 即 ，1 j n。 当bj-10时，前面子段的和对总和有贡献，所以要累加前面的值。bj

8、=bj-1+aj，当bj-1 0时，前面子段的和对总和没有贡献，要重新累加， bj =aj。由此可得计算bj的动态规划递归式bj=maxbj-1+aj，aj， 1 j n。,算法设计：,举例：,11,其中： 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,int n) int sum = 0,b = 0; for(int i=0;i0) b+=

9、ai; else b = ai; if(bsum) sum = b; return sum; ,这已经是一个简化后的算法，最基本的做法其实可以申请一个bn数组，每次求解bj=maxbj-1+aj，aj ，最后遍历bn求得最大数组即可。,子段和问题的扩展2维最大子段和,13,二维最大子段和问题又称为最大子矩阵问题,给定一个m行n列的整数矩阵a，试求矩阵a的一个子矩阵，使其各元素之和为最大。,即 最大子矩阵和问题的最优值为,14,如图所示，在二维最大子段和问题中，我们要求的是这样一个子矩阵，如图中红框所示，其中 0 i j m-1 , 0 p q n-1。,例子1： 0 -2 -7 0 9 2 -

10、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,动态规划法其实就是把二维最大子段和转化为一维最大子段和问题。,转化方法：,我们把这个矩阵划分成n个“条”，条的长度为1到m，通过两个for遍历所有长度的条。 然后，若干个连续的条，就是一个子矩阵了，这样问题就轻易地转化为一维最大子段和问题了。 通过求所有这种条，起点为i，长度为1到m-i+1的“条”的最大子段和，就可以求出整个矩阵的最大子矩阵了。,17,具体枚举长条的时候，同一起点的长度，由于“

11、条”的不同长度间可以利用之前的结果。 比如令bkij表示第k个长“条”区间从i到j的和，那么bkij+1 = bkij+ajk。 当然，实际编程的时候，由于之前的结果求完一维最大子段和后，便不需要保存，所以只需要一维数组b即可。,参考代码,18,public static int MaxSum(int a,int m,int n) int sum = 0; int b =new intn; for(int i = 0;i sum) sum = max; return sum; ,由于MaxSubsum()需要 O(n)的时间，估此算法的双重for循环需要 O(m2n)的计算时间 特别的： 当m

12、= 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)表示前j个元素(必定包含第j个元素)分为互不相交的i段所得的最大i子段和并且i=j。 (注：b(i,j)不一定是最优最大i子段和) 因此在考虑第j个元素时，可能存在两种情况： 1）第j个元素和前一个元素一起包含在第i段中； 2）第j个元素独自划

13、分在第i段中。 根据问题的分析，两种情况分别如下： 1）b(i,j-1)表示第j-1个元素的最大j子段和,所以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 ：,i段,0 1 2 3,0 1 2 3 4 5 6,b(i,j)=maxb(i,j-1)+aj,max

14、 b(i-1,k)+aj,其中k=i-1.j-1.,第 元素,j,因为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 3,0 1 2 3 4 5 6,i段,第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表：,其实很简单，我

15、们最后来一个遍历算法（for循环），遍历所有的bmmn取得其中的最大值就行了。,代码： 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 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(mn2)的计算时间和O(mn)空间,算法改进： 注意到算法中计算bij时只用到了数组b的第i-1行和第i行的值，因此只要存储数组b的当前行，不必存储整个数组（节省空间开销）；另外，max b(i-1,t) （其中i-1=tj）的值可以再计算第i-1行时预先计算并保存起来，这样就不必重新计算，节省计算时间。,public st