文档介绍：ch10ch10算法优化策略算法优化策略? 算法设计策略的比较与选择? 动态规划加速原理? 问题的算法特征? 优化数据结构? 小结与练习? 算法设计策略的比较与选择? 动态规划加速原理? 问题的算法特征? 优化数据结构? 算法设计策略的比较与选择算法设计策略的比较与选择??最大子段和问题最大子段和问题给定由n个整数(可能为负整数)组成的序列a1,a2,…,an,求该序列形如的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依此定义,所求的最优值为:???????????jikknjia1max,0max??jikka int maxSummaxSummaxSummaxSum() { int n=-1; int sum=0;forforforfor (int i=1;i<=n;i++) { int thissum=0;forforforfor (int j=i;j<=n;j++) { for for for for (int k=i;k<=j;k++) thissum+=a[k]; if (thissum>sum) { sum=thissum;besti=i;bestj=j;}}returnreturnreturnreturn sum;}?简单算法 thissum+=a[j]; thissum+=a[j]; thissum+=a[j]; thissum+=a[j]; 注意到,则可将算法中的最后一个for循环省去,避免重复计算只需要O(n2)的计算时间。???????1jikkjikjkaaa?分治算法如果将所给的序列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]最大子段和相同;(3)a[1:n]的最大子段和为 , 且1≤i≤n/2, n/2+1≤j≤n。复杂度分析由以上递归式可得:T(n)=O(nlogn)O(nlogn)O(nlogn)O(cnnOnTOnT???????)()2/(2)1()(??jikka?动态规划算法记,1? j ?n,则所求的最大子段和为当b[j-1]>0时b[j]=b[j-1]+a[j],否则b[j]=a[j]。由此可得计算b[j]的动态规划递归式}][{max][1?????jikjikajb][max][maxmax][max1111jbkakanjjikjinjjiknji???????????????b[j]=max{b[j-1]+a[j],a[j]},1? j ?n?算法maxSumint maxSummaxSummaxSummaxSum() { int n=-1; int sum=0, b=0;forforforfor (int i=1;i<=n;i++) {ifififif (b>0) b+=a[i];elseelseelseelse b=a[i];ifififif (b>sum)sum=b; }returnreturnreturnreturn sum;}算法显然需要O(n)计算时间和O(n)空间。?最大子段和问题的推广最大子段和问题的推广最大子段和问题的推广最大子段和问题的推广记最大子矩阵和问题的最优值为给定一个m行n列的整数矩阵a,试求矩阵a的一个子矩阵,使其各元素之和为最大。?????2121]][[)2,1,2,1(iiijjjjiajjiis)2,1,2,1(max211211jjiisnjjmii??????》最大子矩阵和问题时间复杂性:由于解最大子段和问题的动态规划算法需要时间O(n),故算法的双重for循环需要计算时间O(m2n)。》最大m子段和问题问题描述:给定由n个整数(可能为负整数)组成的序列a1,a2,…,an,以及一个正整数m,要求确定序列的m个不相交子段,使这m个子段的总和达到最大。解题思路:设b(i, j)表示数组a的前j项中i个子段和的最大值,且第i个子段含a[j](1? i ?m, i? j ?n)。则所求的最优值显然为与最大子段和问题类似,计算b(i, j)的递归式为初始时,b(0, j)=0,(1? j ?n);b(i, 0)=0,(1?