在这一章中，作者对同一个问题依次介绍了4种不同时间复杂度的算法，算法的执行速度依次变得更快。据此阐述了作者的（其实也是被普遍认同的）一个观点：复杂深奥的算法有时可以极大地提高程序性能。（纵然在体系结构领域结论往往是相反的。）

• 问题

　　来自一维模式识别的问题。问题的输入是具有n个浮点数的向量x， 输出是输入向量的任何连续子向量中的最大和。（返回的是和的值，不必返回起始下标值。）
　　当所有数都是正数时，最大的子向量就是整个输入；当所有输入都是负数时，总和最大的子向量为空向量，其总和为0。

• 简单算法

　　对所有满足0 ≤ i ≤ j ≤ n 的 (i, j) 整数对进行迭代。对每个整数对，程序都要计算 x[i..j]的总和，并检验总和是否大于迄今为止的最大总和。算法1的伪代码：

maxsofar = 0
    for i = [0, n)
　　    for j = [i, n)
            sum = 0
            for k = [i, j]
                sum += x[k]
            /*sum is sum of x[i..j]*/
            maxsofar = max(maxsofar, sum)

　　显而易见，该算法的时间复杂度为O(n³)，在空间上几乎没有额外开销。

• 平方复杂度算法

通过对算法1的简单改进，去除其中的重复计算部分，就可以把复杂度为O(n³)的算法1改进为复杂度为O(n²)的新算法。

第一种改进着眼于“x[i..j]的总和与前面已经计算出的x[i..j-1]的总和密切相关”。算法2a的伪代码为：

maxsofar = 0
for i = [0, n)
    sum = 0
    for j = [i, n)
        sum += x[j]
        /*sum is sum of x[i..j]*/
        maxsufar = max(maxsofar, sum)

　　这个算法时间复杂度为O(n²)，在空间上也没有额外开销。

　　第二种改进着眼于对数据进行预处理，通过在外循环执行之前就已构建的数据结构的方式在内循环中计算总和。cumarr中的第i个元素包含x[0..i]中的各元素累加和，所以x[i..j]中各个数的总和可以通过计算cumarr[j]-cumarr[i-1]得到。从而我们可以得到算法2b：

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] - cumarr[i-1]
        /* sum is sum of x[i..j]*/
        maxsofar = max(maxsofar, sum)

　　算法2b的时间复杂度同样为O(n²)，在空间上的额外开销为n，即用来存储cumarr数组。

• 分治算法

　　要解决规模为n的问题，可递归地解决两个规模近似为n/2的子问题，然后对它们的答案进行合并以得到整个问题的答案。
　　在本例中，将大小为n的向量划分为两个近似相等的子向量，分别为a和b。

　　然后递归找出a、b中元素总和最大的子向量，分别成为m_a和m_b。

　　最后，问题的解要么整个在a中，要么整个在b中，要么跨越a和b的边界，称其为m_c。

　　进一步地，m_c在a中的部分是a中包含右边界的最大子向量，在b中的部分则是包含左边界的最大子向量。算法3的代码为：

float maxsum3(l, u)
    if (l > u) /* zero elements */
        return 0
    if (l == u) /* one element */
        return max(0, x[l])
    m = (l + u) / 2
    /* find max crossing to left */
    lmax = sum = 0
    for (i = m; i >= 1; i--)
        sum += x[i]
        lmax = max(lmax, sum)
    /* find max crossing to right */
    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))

　　算法3的最初调用为：answer = maxsum(0, n-1)
　　该算法的时间复杂度为O(n logn)，额外空间开销可以忽略。

• 线性复杂度的扫描算法

　　扫描算法，算法的基本思路是将已解决的x[0..i-1]问题推广到x[0..i]问题，有点像组合数学里讲到的递推关系，然而得到的算法的效率是惊人的——线性复杂度。
　　前i个元素中，最大总和子数组要么在前i-1个元素中（将其存储在maxsofar中），要么其结束位置为i（将其存储在maxendinghere中）。

maxsofar = 0
maxendinghere = 0
for i = [0, n)
    /* invariant: maxendinghere and maxsofar
      are accurate for x[0..i-1]*/
    maxendinghere = max(maxendinghere + x[i], 0)
    maxsofar = max(maxsofar, maxendinghere)

• 原理总结

　　保存状态，避免重复计算。 算法2和算法4使用了简洁的动态规划形式。通过使用一些空间来保存中间计算结果，我们避免了花时间对其重复计算。

　　将信息预处理至数据结构中。 算法2b中的cumarr结构允许对子向量中的总和进行快速计算。

　　分治算法。 算法3使用了简单的分治算法形式。

　　扫描算法。 与数组有关的问题通常可以通过思考“如何将x[0..i-1]的解扩展为x[0..i]的解？”来解决。

　　累积。 算法2b使用了一个累积表，这一类表常用于处理有范围限制的问题。

　　下界。 只有在确定了自己的算法是所有可能的算法中最佳的算法以后，算法设计师才可能踏踏实实地睡个好觉。