程式設計珠玑第八章-算法設計技術

本章就一個小問題研究了四種不同的算法，重點強調了這些算法的設計技術，綜合本章内容，告訴我們：複雜深奧的算法有時可以極大地提高程式性能。

問題定義： 具有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.下界。确定相比對的下界。