Ch10-常用算法课程.pdf

ch10 算法优化策略 ch10 算法优化策略 • 10.1 算法设计策略的比较与选择 • 10.1 算法设计策略的比较与选择 • 10.2 动态规划加速原理 • 10.2 动态规划加速原理 • 10.3 问题的算法特征 • 10.3 问题的算法特征 • 10.4 优化数据结构 • 10.4 优化数据结构 • 10.5 小结与练习 • 10.5 小结与练习 10.1 算法设计策略的比较与选择 10.1 算法设计策略的比较与选择 • 最大子段和问题 • 最大子段和问题 给定由 个整数 可能为负整数 组成的序列 n ( ) j a ,a ,…,a ,求该序列形如 的子段和的最 1 2 n  a k k  i 大值。当所有整数均为负整数时定义其最大子 段和为０。依此定义，所求的最优值为:  j  max 0, max a   k 1i jn ki   • 简单算法 maxSum int mmaaxxSSuumm() { int n=a.length-1; int sum=0; for ffoorr (int i=1;i=n;i++) { int thissum=0; for ffoorr (int j=i;j=n;j++) { for ffoorr (int k=i;k=j;k++) thissum+=a[k]; thissum+=a[j]; tthhiissssuumm++==aa[[jj]];; if (thissumsum) { j j1 sum=thissum; a  a a k j k 注意到 ，则可将算 besti=i; ki ki 法中的最后一个for循环省去， bestj=j; 避免重复计算只需要 2 的 } O(n ) } 计算时间。 return rreettuurrnn sum;} • 分治算法