当前位置：首页 -> AI编程基础 -> JAVA

返回连续子序列，使得和最大（变形）

2014-11-24 01:08:50 · 作者: · 浏览: 0
标签: 返回 连续 序列 使得 最大 变形
编程珠玑上一道老题：一个数组，找出连续子序列使得和最大。我们可以使用线性扫描的算法来解决，这道题变形之后成为：找出连续子序列，使得和最接近某个数。原来的时间复杂度为线性的方法行不通了，我们可以累加数组，然后排序，求的相邻的差，最接近k的数就是所求。代码如下：
  1. int approximate(int * pArry, int len)
  2. {
  3. int * cum = 0;
  4. int * realarry = new
    int[len + 1];
  5. realarry[0] = 0;
  6. cum = realarry + 1; //cum[-1] = 0
  8. //累计pArry[0....i]的和存放于cum[i]中
  9. for (int i = 0; i < len; i++)
  10. {
  11. cum[i] = cum[i - 1] + pArry[i];
  12. }
  13. sort(cum, cum + len); //对cum排序
  14. int iMin = cum[1] - cum[0];
  15. for (int k = 1; k < len; k++)
  16. {
  17. iMin = min(iMin, cum[k] - cum[k - 1]); //返回相邻两个元素差值最小的
  18. }
  19. return iMin;
  20. }