限制时空的循环左旋小节中描述了算法对程序的一方面影响：
好的算法思路会使程序更加简单。
这一回我们将会讲到另一方面: 复杂深奥的算法有时可以极大的提高程序性能。
1.简单问题与简单想法
问题来自一维空间的模式识别：
输入一串n个整数的向量，求其中任何连续子向量空间中的最大和情况。
如：
31 -41 59 26 -53 58 97 -93 -23 84
2 6
ans is x[2..6] == 187
程序的输出应该为 187, 即 59+26-53+58+97
当然，我们稍一思索就有了简单答案：
A:
maxsofar = 0
for i = [0, n)
for j = [i, n)
sum = 0
for k = [i,j]
sum += x[k]
maxsofar = max(sum, maxsofar)
上面的算法对于每一个向量 x[i..j] 都求 sum(x[k]) (i<=k<=j)
2. 接下来的算法提取出了算法A中明显反复计算的部分
B:
maxsofar = 0
for i = [0, n)
sum = 0
for j = [i, n)
sum += x[j]
/* for every j, sum mean sum of x[i..j]*/
maxsofar = max(maxsofar, sum)
显然下一种算法也是O(n^2)的
cumarr[-1] = 0
for i = [0, n)
cumarr[i] = cumarr[i-1] + x[i]
maxsofar = 0
for i = [0, n)
for j = [i, n)
sum = cumarr[j] - cummarr[i-1]
maxsofar = max(maxsofar, sum)
3. 接下来采用分治算法，使时间复杂度降低至 O(nlogn)
该题分治思想：
对于一个向量x[i..j] 内最大子向量的求解，
事实上是对 x[i..(i+j)/2] 与 x[(i+j)/2 +1 .. j] ，
和 x[k .. l] (k>i, l < j )(即跨越中间界的最大子向量)，
三个分问题的求解。
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>=1; 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, maxsum3(l, m), maxsum3(m+1, u))
当然实际上该算法也有缺陷，速度达到O(nlogn), 分治时最空间的要求也会增加，数据量达到10W时，
分治时的栈操作过于频繁而且跳转频繁，事实上也不是一个理想的算法。
4. 对于从o(n^2)降到O(nlogn)的算法，我们仍然想对其继续优化，
扫描算法：
对于x[i .. j] 向量，从最左端扫描至最右端，我们可以确定的是，最优答案所处的位置，
要么包含在 x[i .. j] 中 (如 maxsofar), 要么和后面的向量衔接，必包含 x[j] (如maxendinghere)
-
….
-
maxsofar
-
….
-
maxendinghere
maxsofar = 0
maxendinghere = 0
for i = [0, n)
maxendinghere = max(maxendinghere + x[i], 0)
maxsofar = max(maxsofar, maxendinghere)
运行时间为O(n), 我们称其为线性算法， 到此已经优化到极致了。
背后的故事：
最早提出问题的是布朗大学Ulf Grenander 面对一个模式匹配的问题，最初形式是二维向量的模式匹配，
Grenander将其化简为一维以便深入了解分析。
Grenander首先设计了算法1和算法2，并在1977年叙述给Michael Shamos,
后者花了一通宵设计出算法3，当时人们一致认为已经是很好的算法了。
而后Shamos在CMU(卡内基梅隆大学)研讨会上介绍的该问题及其历史，
结果与会的统计学家 Jay Kadane 在一分钟之内就勾勒出算法4，还好不会有更快的算法了，
因为任何正确的算法都至少需要O(n)时间。
虽然一维问题得到了完美解决，二维的问题却迟迟没有解决，
《编程珠玑》上提到到第二版将发行时(08年)，问题被提出了20年，所有已知的算法都被认为开销过大而没有实装。