最大投资回报问题：暴力解法 下面的过程遍历的顺序为： (0,0),(0,1),.,(0,n-1)（1,1)(1,2),,(1,n-1),.(n-2,n-2),(n-2,n-1),(n-1,n-1) MaxSum =0; for (i=0;i<N;i++) the sequence ThisSum=0; =0 for (j=i;j N;j++) 1 =2 ThisSum+=A[j]; if(ThisSum>MaxSum) MaxSum ThisSum; } } in O(n2) =n-1 return MaxSum;
最大投资回报问题：暴力解法 MaxSum = 0; for (i = 0; i < N; i++) { ThisSum = 0; for (j = i; j < N; j++) { ThisSum += A[j]; if (ThisSum > MaxSum) MaxSum = ThisSum; } } return MaxSum; the sequence i=0 i=1 i=2 i=n-1 j in O(n2 ) 下面的过程遍历的顺序为： (0,0), (0,1), …, (0,n-1); (1,1), (1,2), …, (1,n-1), …… (n-2,n-2), (n-2, n-1), (n-1,n-1)
用分治法解最大子数组问题 Part 1 Part 2 the sub with largest sum may be in: recursion Part 1 Part 2 or: The largest is the result Part 1 Part 2 问题5：跨中点的部分如何计算？
用分治法解最大子数组问题 Part 1 Part 2 the sub with largest sum may be in: Part 1 Part 2 or: Part 1 Part 2 recursion The largest is the result
FIND-MAXIMUM-SUBARRAY(A,low,high) 非递归代价：常量 1 if high ==low 2 return (low,high,Allow /base case:only one element 3 else mid =[(low +high)/2] 4 (left-low,lefi-high,left-sum)= 递归，理想状况下 FIND-MAXIMUM-SUBARRAY(A,low,mid) 问题规模是原来的 5 (right-low,right-high,right-sum)= 一半。 FIND-MAXIMUM-SUBARRAY(A,mid +1.high) 非递归代价： 6 (cross-low,cross-high,cross-sum)= 线性 FIND-MAX-CROSSING-SUBARRAY(A,low,mid,high) 7 if left-sim≥right-sumn and left-sm≥cross-sm 8 return (lef-low,lef-high,lefi-sum) 9 elseif right-sum z left-sum and right-sum z cross-sum 非递归代价： 10 return(right-low,right-high.right-sum) 常量 11 else return (cross-low.cross-high,cross-sum) O(nlog n
非递归代价：常量 递归，理想状况下 问题规模是原来的 一半。 非递归代价： 线性 非递归代价： 常量 O(nlogn)
矩阵乘法：似乎非得2(m) If A =(a and B=(b)are square nxnmatrices,then in the product C=A.B,we define the entry cij,for i.j=1.2.....n,by SQUARE-MATRIX-MULTIPLY(A,B) 1 n=A.rows 2 let C be a new n x n matrix ci=∑akbj 3 for i 1to n k=1 4 for j=1to n 5 C=0 6 for k Iton 7 C=C十ak·b对 8 return C
矩阵乘法：似乎非得(n 3 )
Suppose that we partition each of A,B.and Cinto four2/2 matrices 4=(）a=()c-(8) so that we rewrite the equation C =A.B as (8)）-(A）() Equation (4.10)corresponds to the four equations C1=A11·B11+A2·B21 C12=A11·B12+A2·B22, 1个n阶方阵相乘的问题 C2I=A21·B11+A22·B21 可以分解为8个n/2阶方 C2 =A21·B12+A22·B22 阵相乘的子问题
1个n阶方阵相乘的问题 可以分解为8个n/2阶方 阵相乘的子问题