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

讲课的主要内容： 问题描述 最大子段和问题的简单算法以及改进算法(枚举/穷举) 最大子段和问题的分治算法 最大子段和问题的动态规划算法 推广1：最大子矩阵问题 推广2：最大m字段和问题算法及改进算法 复杂度分析 满足典型的分治算法递归式 解此递归方程，得T(n)=O(nlogn) 补充内容： 动态规划算法步骤 int MaxSubsum(int m,int n,int a[]){ if(n m || m1) return 0; int b[][] = new int[m+1][]; for(int i = 0;i = m;i++){b[i] = new int[n+1];} for(int i = 0;i = m;i++){b[i][0] = 0;} for(int j = 1;j = n;j++){b[0][j] = 0;} for(int i = 1;i = m;i++){ for(int j = i;j = n-m+i;j++){ //n-m+i确保后面的元素可以够分成 m-i 段 if(ji){ b[i][j] = b[i][j-1] + a[j-1]; for(int k = 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]; } } else b[i][j] = b[i-1][j-1] + a[j-1]; } } int sum = 0; for(int j = m;j = n;j++){ if(sum b[m][j]) sum = b[m][j]; } return sum; } 谢谢！ 最大子段和问题 * * 最大子段和问题 问题描述：给定由n个整数(可能为负整数)组成的序列a1,a2,…,an,求该序列形如 ai,ai+1,…,aj i,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). 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;k=j;k++) thissum+=a[k]; if (thissumsum) { sum=thissum; besti=i; bestj=j; } } } return sum; } 1、枚举算法设计 * 首先用最简单的枚举算法来解决这个问题。枚举所有可能的 起始下标和终止下标，累加求和。并从中选取最大的字段和。 * 改进的枚举算法设计 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;j=n;j++) { if (thissumsum) { sum=thissum; besti=i; bestj=j; } } } return sum; } thissum+=a[j]; 由 知第k次计算的的和可由k-1次的结果递推。 算法1每次都从头开始累加，则可将算法中的最后一个for循环省去，避免重复计算。 改进后的算法只需要O(n2)的计算时间 2、分治算法 经过以上改进只是减少了i一定的重复计算操作,其中仍会有很多重复计算。从这个问题结构可以看出