编程珠玑上一道老题：一个数组，找出连续子序列使得和最大。我们可以使用线性扫描的算法来解决，这道题变形之后成为：找出连续子序列，使得和最接近某个数。原来的时间复杂度为线性的方法行不通了，我们可以累加数组，然后排序，求的相邻的差，最接近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;
-
}
返回连续子序列，使得和最大（变形）,布布扣,bubuko.com
返回连续子序列，使得和最大（变形）
原文：http://blog.csdn.net/gzxcyy/article/details/21297063
