编程珠玑上一道老题：一个数组，找出连续子序列使得和最大。我们可以使用线性扫描的算法来解决，这道题变形之后成为：找出连续子序列，使得和最接近某个数。原来的时间复杂度为线性的方法行不通了，我们可以累加数组，然后排序，求的相邻的差，最接近k的数就是所求。代码如下：
- int approximate(int * pArry, int len)
- {
- int * cum = 0;
- int * realarry = new int[len + 1];
- realarry[0] = 0;
- cum = realarry + 1; //cum[-1] = 0
- //累计pArry[0....i]的和存放于cum[i]中
- for (int i = 0; i < len; i++)
- {
- cum[i] = cum[i - 1] + pArry[i];
- }
- sort(cum, cum + len); //对cum排序
- int iMin = cum[1] - cum[0];
- for (int k = 1; k < len; k++)
- {
- iMin = min(iMin, cum[k] - cum[k - 1]); //返回相邻两个元素差值最小的
- }
- return iMin;
- }