算法导论第四章习题答案（第三版） Introduction to Algorithm
Exercises
4.1-1
若A中的元素都是负数，那么FIND-MAXIMUM-SUBARRAY的返回值是绝对值最小的子数组。
4.1-2
int Max_Subarray(int A[]){
int max=0;
for(int i=0;i<=n;i++)
for(int j=i;j<=n;j++)
if((A[j]-A[i])>max)
max=A[j]-A[i];
return max;
}
4.1-3
对于不同的计算机，结果会略有不同；
改进之后，速度性能会有所提升，性能交叉点不会改变。
4.1-4
最后返回语句的时候，判断结果，若为负数，则返回0。
4.1-5
int Max_Subarray(int A[]){
int max = 0,sum = 0;
for(int i=1;i<=length;i++){
sum = sum + A[i];
if( sum > max )
max = sum;
else if( sum < 0 )
sum = 0;
}
if (max > 0)
return max;
return NULL;
}
如果子数组的累加和小于0，证明最大子数组一定不包含该子数组。
4.2-1.略。
4.2-2.略。
4.2-3
将矩阵补一行0或者列，显然时间复杂度是不变的。
4.2-4
T(n)=kT(n/3)+Θ(n²)。
根据主方法：
可以算出只有当
时，最终式子会由该项决定，而且
，计算出k的值即可。
4.2-5
同上题写出递推公式，利用主方法计算即可。
4.2-6
最快花费时间应该是k的2次方倍的strassen算法运行时间。
颠倒矩阵之后应该是k倍的strassen算法的运行时间。（不怎么会，望大家告知正确答案）
4.2-7.略。
（未完待续）
版权声明：本文为hlj-ljz原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。