清华大学出版社 分治算法 RSITY PRESS 如果将所给的序列a[1:n分为长度相等的2段a[1n/2]和 a[n/2+1n],分别求出这2段的最大子段和,则a1n的 最大乙几和2种娃 (1)复杂度分析 O ≤C (2) T(n)= 27(n/2)+O(n)n>c (3) T(n=o(nlogn) sano 对 子序 列中。因此,可以在a1n/2中计算出 ,并在 a[n/2+1n中计算出 。则ss2即为出现 情形(3)时的最优值。据龀可姗计出求最大子段和的分 治算法。5 分治算法 如果将所给的序列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。 对于情形(3)。容易看出，a[n/2]与a[n/2+1]在最优子序 列中。因此，可以在a[1:n/2]中计算出 ，并在 a[n/2+1:n]中计算出 。则s1＋s2即为出现 情形(3)时的最优值。据此可设计出求最大子段和的分 治算法。 = j k i k a =   = / 2 1 / 2 1 max [ ] n k i i n s a k = + +   = i k n n i n s a k / 2 1 / 2 1 2 max [ ] 复杂度分析 T(n)=O(nlogn) n c n c T n O n O T n      + = 2 ( / 2) ( ) (1) ( )