一、算法设计
1、问题描述：输入具有n个浮点数的向量x，输出是输入向量的任何连续子向量中的最大和。
有效解决方法：
（1）分治算法：要解决规模为n的问题，可递归得解决两个规模近似为n/2的子问题，然后对他们的答案进行合并以得到整个问题的答案。
代码如下，最大子向量要么整个在a中，要么整个在b中，要么跨越a和b之间的边界。跨越a和b 的边界时，其最大子向量在a中的部分包含右边界的最大子向量，在b中的部分包含左边界的最大子向量。算法复杂度为O（nlogn）。
float maxsum3(l, u)
if (l > u) return 0
if (l == u ) return max(0, x[l])
m = (l + u) / 2
lmax = sum = 0
for (i = m; i >= l; i--)
sum += x[i]
lmax = max (lmax, sum)
rmax = sum = 0
for i = (m, u]
sum += x[i]
rmax = max (rmax, sum)
return max(lmax+rmax, maxsum(l, m), maxsum3(m+1, u))
（2）一个O（n）复杂度的算法，从最左端（元素 x[0]）开始，一直扫描到最右端（元素 x[n-1]），记下所碰到过的最大总和子数组。最大值初始为0.假设已经解决了针对 x[0..i-1] 的问题，现在需要拓展到 x[i] 中。可以使用类似分治法中的道理，前 i 个元素中，最大总和子数组要么在 i-1 个元素中（存储在 maxsofar 中），要么截止到位置 i（存储在 maxendinghere中）。算法代码更加简短，但是运行起来是最快的，运行时间是O(n)，已经是线性算法。源代码如下：
float max_subvector5(float array[], int length)
{
int i;
float maxsofar = 0, maxendinghere = 0;
for(i = 0; i < length; i ++)
{
maxendinghere = (maxendinghere + x[i]) > 0 ? maxendinghere : 0;
maxsofar = maxsofar > maxendinghere ? maxsofar : maxendinghere;
}
return maxsofar;
}
二、总结
本章故事中的这些算法给出了几个重要的算法设计技术：
1、保存状态，避免重复计算。通过使用一些空间来保存中间计算结果，我们避免了花时间来对其重复计算。
2、将信息预处理到数据结构中。
3、分治算法。
4、扫描算法。与数组相关的问题经常可以通过思考“如何将x[0...i-1]的解扩展为x[0...i]地解来解决。
5、累积。
6、下界。确定相匹配的下界。
三、习题
1、习题10：假设我们要查找的是总和最接近0的子向量，而不是具有最大总和的子向量，则如何设计算法？若查找总和最接近某一个给定实数t的子向量呢？
解答：初始化累积数组cum，使得cum[i] = x[0] + ... + x[i]。如果cum[l-1] = cum[u]，那么子向量x[l...u]之和就为0.所以可以通过定位cum中最接近的两个元素来找出和最接近零的子向量，可通过排序累积数组并比较相邻元素间的大小从而得到结果。找最接近某一特定值的算法类似这样。
2、习题13：在最大子数组问题中，给定m*n的实数数组，我们需要求出矩形子数组的最大总和。该问题的复杂度如何？
解答：可以在长度为m的维度上使用平方复杂度的算法，而在长度为n的维度上使用线性算法。可以在O（m^2*n)的时间复杂度内解决m*n问题。代码如下所示：
float max_subarr(float **array, int row, int col)
{
int i, j, k;
float *vector, max = 0, maxsofar, maxendinghere;
assert(row > 0 && col > 0);
vector = (float *) malloc(col * sizeof(float));
assert(vector != NULL);
printf("the array :\n");
for( i = 0; i < row; i ++)
{
memset(vector, 0, col * sizeof(float));//初始化为0
for( j = i; j < row; j ++)
{
//vector[k]的值为行i至行j的第k列元素之和，把二维问题转化为一维问题。
for(k = 0; k < col; k ++)
vector[k] += array[j][k];//vector[k] = array[i][k] + array[i + 1][k] + ... + array[j][k],
maxsofar = vector[0];
maxendinghere = 0;
for(k = 0; k < col; k ++)
{
maxendinghere = (maxendinghere + vector[k]) > 0 ? (maxendinghere + vector[k]) : 0;
maxsofar = maxsofar > maxendinghere ? maxsofar : maxendinghere;
}
max = max > maxsofar ? max : maxsofar;
}
}
return max;
}