4-1-1：
返回绝对值最小的负数即：最大的负数
4-1-2：
BRUTE-FORCE-FIND-MAXSUB(A)
max-sum=-INF
for i=1 to A.length
sum=0;
for j=i to A.length
sum+=sum[j]
if sum>max-sum
max-sum-=sum
low=i
high=j
return (low,high,max-sum)
4-1-3：
关于如何测试性能，我不会。。。请读者指教。不过http://www.cnblogs.com/Jiajun/archive/2013/05/08/3066979.html提供了数据，说明了大多数情况下，我们需要的可能是暴力算法
4-1-4：
算法所有的return项都0比较，如果max-sum小于0，则返回空数组。
4-1-5：
这里就是说的动态规划的思想，更具体的是增量法，增量法的具体说明见《插入排序》
这里如果已知A[1..j]的最大子数组设为max_sub[j],那么求max_sub[j+1]:
则有两种情况：
- 等于max_sub[j]
- 等于以A[j+1]结束的某个子数组A[i..j+1]
所以max_sub[j+1]=max( max_sub[j]，A[i..j+1](1<=i<=j+1) )
这里求以j+1结尾的最大子数组是线性时间，所以说，如果按上面等式运算的话，复杂度为theta(n^2)，性能还不如分治法，那么还有什么可用信息？
以j+1结尾的最大子数组等于以j结尾的最大子数组加上A[j+1]。
以max_end[j]表示以j结尾的最大子数组的话，那么：
max_sub[j+1]=max{ max_sub[j], max_end[j]+A[j+1], A[j+1] }
max_end[j+1]=max{ max_end[j]+A[j+1],A[j+1] }
只要维护好这两个等式就能在线性时间内得出结果：
伪码：
FIND-MAXSUB(A)
//此处为了方便，所以max-sub和max-end使用了一样的数据结构
let max-sub[1..A.length] and max-end[1...A.length] be new arrays and structure is (low,high,value)
//以（low，high，value)方式表示
max-sub[1]=(1,1,A[1])
max-end[1]=(1,1,A[1])
for i=2 to A.length
if max-sub[i-1].value>max-end[i-1].value+A[i] and max-sub[i-1].value>A[i]
max-sub[i]=max-sub[i-1]
else if max-end[i-1].value+A[i]>=max-sub[i-1].value and max-end[i-1].value+A[i]>A[i]
max-sub[i]=(max-end[i-1].low,i,max-end[i-1].value+A[i])
else
max-sub[i]=(i,i,A[i])
if max-end[i-1].value+A[i]>A[i]
max-end[i]=(max-end[i-1].low,i,max-end[i-1].value+A[i])
else
max-end[i]=(i,i,A[i])
return max-sub[A.length]
根据伪码，我们得知，T(n)=theta(n)
C++实现：
struct MaxSubArray
{
int low;
int high;
int sum;
};
void find_maxSub(int* A,int A_length,MaxSubArray* result)
{
MaxSubArray* max_sub=new MaxSubArray[A_length];
MaxSubArray* max_end=new MaxSubArray[A_length];
//初始化条件,c++程序与伪代码不同：是从0开始索引
max_sub[0].sum=A[0];
max_sub[0].low=max_sub[0].high=0;
max_end[0].sum=A[0];
max_end[0].low=max_end[0].high=0;
for(int i=1;i<A_length;++i){
if(max_sub[i-1].sum>max_end[i-1].sum+A[i] && max_sub[i-1].sum>A[i]){
max_sub[i]=max_sub[i-1];
}else if(max_end[i-1].sum+A[i]>=max_sub[i-1].sum &&max_end[i-1].sum>0){
max_sub[i].sum=max_end[i-1].sum+A[i];
max_sub[i].low=max_end[i-1].low;
max_sub[i].high=i;
}else{
max_sub[i].sum=A[i];
max_sub[i].low=max_sub[i].high=i;
}
if(max_end[i-1].sum>0){
max_end[i].sum=max_end[i-1].sum+A[i];
max_end[i].low=max_end[i-1].low;
max_end[i].high=i;
}else{
max_end[i].sum=A[i];
max_end[i].low=max_end[i].high=i;
}
}
*result=max_sub[A_length-1];
}
其实这个题本身没这么复杂，有更简单的线性方法，不过这里要求可以是空数组，即最大值必然>=0：
从前往后累加，如果当前子数组的累加和小于零，则意味着最大子数组(maximun subarray)肯定不包括该子数组，所以果断舍弃，重新开始累加。
伪码：
FIND-MAXSUB(A)
max-sum=-INF
sum=0
low=1
high=1
for i=1 to A.length
sum=sum+A[i]
if sum>max-sum
max-sum=sum
high=i
//如果A[low..i]<0，那么小于0的元素必然在A[j,,,i]，即：在后半段，那
//么这一段必然不包含在最大子数组中
if sum<0
low=i+1
sum=0
return (low,high,max-sum)
c++实现：
void find_maxSub(int* A,int A_length,MaxSubArray* result)
{
int max_sum=-INF;
int sum=0;
int low=0;
int high=0;
for(int i=0;i<A_length;++i){
sum+=A[i];
if(sum>max_sum){
max_sum=sum;
high=i;
}
//如果A[low..i]<0，那么小于0的元素必然在A[j,,,i]，即：在后半段，那么这一段必然不包含在最大子
//数组中，此时，low必然从i+1开始，把sum置零，重新累加
if(sum<0){
sum=0;
low=i+1;
}
}
if(max_sum>0){
result->low=low;
result->high=high;
result->sum=max_sum;
}else{
result->low=result->high=-1;//表示是个空数组
result->sum=0;
}
}
4-2-X：
可以看看这位大神的博客：http://www.cnblogs.com/Jiajun/archive/2013/05/08/3066979.html
4-5（芯片检测）
a. 如果超过n/2个坏芯片，假设，每个坏芯片都会说其他芯片是坏的；那么对于任意两个芯片，都会说对方是坏的，没有好的。
b.假设有a个好芯片，b个坏芯片，其中（a>n/2,b<n/2);进行n/2次逐对检验，对于一对都说对方是好的芯片，我们只留下任意一个，对于其他情况，统统丢弃掉；
1.恰好a中的芯片与a中的芯片配对；b中的芯片与b中的芯片配对；a中芯片配对时，两个芯片都是好的，必然都说对方是好的，所以会留下的好芯片数a'=a/2，b中的配对结果有很大的随机性，但是留下的芯片数b'：0<b'<b/2,
其中当b'=0时，此时每个坏芯片都说对方是坏的；
当b'=b/2时，此时每个坏芯片都说对方是好的；
此时的子问题是：总共有(a'+b')个芯片，其中a'个好芯片，b'个坏芯片：
芯片数：a'+b'<a/2+b/2<n/2;所以至少使问题规模减半；
好芯片比例：a'/(a'+b') > a/(a+b) > 1/2；所以好芯片数大于n'/2的条件依然满足；
2.当b中的芯片全部都与a中的芯片配对时；此时a,b配对的，两个芯片一个是好的，一个是坏的，会被全部丢弃；
剩下的(a-b)个好芯片配对，两个芯片都是好的，会保留一个；此时：
剩余a'=(a-b)/2个好芯片，b'=0个坏芯片；
芯片数：n'=a'+b'=(a-b)/2<n/2;所以至少使问题规模减半；
好芯片比例为1>1/2;依然满足条件；
3.当b中部分芯片（b1个）与a中芯片配对；此时a中与b1配对的，会全部丢弃；
b中剩余(b-b1)个坏芯片自己配对，结果具有很多随机性，但是留下的坏芯片数b'：0<b'<(b-b1)/2;
a中剩余(a-b1)个好芯片自己配对，会留下一个，此时好芯片数a'：a'=(a-b1)/2;
此时：
芯片数n'=a'+b'<(a+b-2*b1)/2<n/2;
好芯片比例：a'/(a'+b')=(a-b1)/(a+b-2*b1)>1/2
综上所述：
进行n/2次逐对比较足以将问题规模减半；
c.T(n)=T(n/2)+O(n)
经递归树方法得：T(n)=theta(n);
4-6(Monge阵列)
a.
b.迭代处理2*2矩阵即可；
c.证明：
