程式設計珠玑第8章

正文中所提及的算法可以在

ecnu oj 1109上面找到。

template<typename T>
T maxSubSum(T *a, int n)
{
       T s = 0, t = 0, mx = a[0];
       for (int i = 0; i < n; ++i)
       {
               mx = mx > a[i] ? mx : a[i];
               t = t < 0 ? a[i] : t + a[i];
               s = t > s ? t : s;
       }
       if (mx > 0) return s;
       return mx;
}
           

習題1、2、3、略去

4、需要測試？這個比較難算

5、6、（6題看2.2的答案有點意思。）

7、8、略去

9題

如上面所寫的程式把return mx 改為return 0;

10、設定s[i] = sum(a[0] .... a[i]) ，那麼尋找s數組中最接近的兩個數即可。

         如果要是找最接近t的數，那麼處理方法與上面一樣，隻不過是求兩個數絕對值最接近t。複雜度nlogn

11、中文翻譯得實在是~~~大意如下：給定一個數組S，你需要給出S[i~j]和。也就是S[i] + S[i+1] ~~~S[j]。

        要求是O(1)可以得到，并且O(n)的空間複雜度。

        處理方式與10題一樣。

12、沒看懂

13、在程式設計之美中有提及，不過算法複雜度不是最好的。

14、建立兩個輔助數組C, D

        c[i] = a[0] + ~~~~+ a[i-1]

        d[i] = a[i+1] + ~~~~a[n-1]

        首先求得整個數組的和S

        那麼X[i] + ~~ + X[i+m] = S - c[i] - d[i+m+1];

       在O(n)的時間可以求解。

15、NlgN