编程珠玑第八章-算法设计技术

本章就一个小问题研究了四种不同的算法，重点强调了这些算法的设计技术，综合本章内容，告诉我们：复杂深奥的算法有时可以极大地提高程序性能。

问题定义： 具有n个浮点数的向量x，求出输入向量的任何连续子向量的最大和。

立方算法：

maxsofar = 0;

for i = [0,n)

    for j=[i,n)

        sum = 0;

        for k=[i,j]

           sum += x[k]

           maxsofar = max(maxsofar,sum);

平方算法：

maxsofar = 0;

for i =[0,n)

    sum = 0;

    for j=[i,n)

        sum+= x[j]

        maxsofar= max(maxsofar,sum);

分治算法：

float maxsum3(l,u)

        if(l>u)

               return 0;

        if(l==u)

               return max(0,x[l]);

        lmax= sum = 0;

        for(i=m;i>=l;i--)

               sum += x[i];

               lmax=max(lmax,sum);

        rmax = sum= 0;

        fori=(m,u]

               sum += x[i]

               rmax = max(rmax,sum);

        returnmax(lmax+rmax,maxsum3(l,m),maxsum3(m+1,u));

调用方法： answer = maxsum3(0,n-1)

线性算法：

maxsofar = 0;

maxendinghere = 0;

for i =[0,n)

        maxendinghere= max(maxendinghere+x[i],0);

        maxsofar= max(maxsofar,maxendinghere);

本章故事中的这些算法给出了几个重要的算法设计技术：

1.保存状态，避免重复计算。通过使用一些空间来保存中间计算结果，我们避免了花时间来对其重复计算。

2.将信息预处理到数据结构中。

3.分治算法。

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

5.累积。

6.下界。确定相匹配的下界。