编程珠玑第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