从一个数列中取具有最小和的子序列

问题描述:给定一个含有 n 个元素的数列,元素有正有负,找出和最小的一组相邻的数。即给定 a[n],求 i,j 使得 a[i] + a[i+1] + ...+ a[j] 的和最小。

这个问题1并不难,但是我在想这个问题时经历了比较有趣的思考过程,写下来给大家分享一下。

其实这道题主要考察的是问题转换(或者说是抽象?)的能力,即如何将一个看似复杂的问题转换成一个简单的问题。直接求一个连续子列的和看起来很麻烦,我们要考虑 i 和 j 的取值,然后把子列中的元素加起来。但是换一个角度,一个连续子列的和可以看成是两个前缀和相减,比如:a[i] + a[i+1] + ...+ a[j] 实际上就等于 s[j] - s[i-1],其中 s[k] = a[0] + a[1] + ... + a[k]。这在高等数学中也是会被经常用到的方法。

所以我们要做的就是

计算出前缀和序列 s[n],并找出最小的 s[j] - s[i],其中 j>i,且 j,i 属于 {0,1,...,n}。

如果不要求 j>i,那么答案很简单,s[n] 中最小值减去最大值就是结果。但既然要求了 j>i,就不能这样做了,因为最小值的位置未必在最大值后面。最显而易见的方法就是遍历了:

J = 1; I = 0;
for (i=0; i<n; i++) {
  for (j=i+1; j<n; j++) {
    if (s[j] - s[i] < s[J] - s[I]) {
      I = i; J = j;
    }
  }
}

但是这个算法很耗时,两层嵌套,等差数列求和,复杂度肯定是 O(n2)。观察一下数列的规律我们可以发现,如果 s[i] < s[I] 的话,我们就没有必要计算 s[j] - s[i],因为结果肯定比 s[j] - s[I] 大嘛,同理可以用于 s[j] > s[J] 的情况,这样呢,我们可以稍微优化一点儿:

J = 1; I = 0;
for (i=0; i<n; i++) {
  if (s[i] < s[I]) continue;
  for (j=i+1; j<n; j++) {
    if (s[j] > s[J]) continue;
    if (s[j] - s[i] < s[J] - s[I]) {
      I = i; J = j;
    }
  }
}

但是这个优化作用到底有多大?我没有仔细计算,是比第一种情况快了一点儿,但最显著的速度提升还是在于第一层循环中,那样就能减少 n-i+1 次计算,在最坏的情况下仍然是 O(n2)。所以我觉得仍然不够,不就求一个最小值嘛,为什么那么慢呢,肯定是因为我笨。于是我就在 BBS 求助了一下别人,果然有人给出更快的算法:

J = 1; I = 0; max = 0;
for (i=1; i<n; i++) {
  if (s[i]-s[max] < s[J]-s[I]) {
    I = max;  J = i;
  }
  max = s[i] > s[I] ? i : max;
}

这个算法的思想是: s[I] 肯定是 s[J] 之前最大的数,s[J] 也是 s[I] 之后最小的数,那么保留到目前为止最大的数 s[max],用当前数 s[i] 去减它(肯定是小于 s[i] - s[I] 的),看它是否小于 s[J] - s[I],如果是的话,那么 s[i] -s[max] 就是到 i 为止最小的差值对。扫描一遍 s[n] 就能得到结果,O(n)!

后来我发现在 Jon Bentley 的《编程珠玑》第二版第8章讨论了这个问题1(只不过是讨论的最大值),在该章最后提出的算法4中,仅仅使用了与上面算法相同的扫描方法,而没有使用累加操作。虽然上面算法复杂度与算法 4 相同,但算法 4 复杂度中 n 的系数要小一些,下面是算法 4 的 C 语言实现:

int i = 0, I = 0, J = 0, I_end = 0;
int max_end = 0, max_sofar = 0;
for (i=0; i<len; i++) {
  max_end += a[i];
  if (max_end > 0) {
    max_end = 0; I_end = i;
  }
  if (max_sofar > max_end) {
    max_sofar = max_end;
    I = I_end; J = i;
  }
}

[1] 2008年1月15日注:这个问题出现在《Programming Pearls》第二版的 Column 8,Jon Bentley 对该问题的起源和算法发展做了非常详致的分析。

《从一个数列中取具有最小和的子序列》上有13条评论

  1. 没记错的话 Programming Pearls 第二版里有这个问题。

  2. 最后一个貌似叫online算法,最近碰巧也看到这么一个题......

  3. 不需要计算前缀和序列吧。我的思路是,线性扫描数组,并维护两个数据:当前最佳答案min,以及以当前元素结尾的最佳答案x。那么,扫描到下一个元素arr[i+1]时,如果x>0,则新的x只取arr[i+1]而不包含前面的内容;否则新的x包含旧的x以及arr[i+1]。同时更新min。没有经过深思熟虑,如有错误请指正。下面是Haskell程序。

    -- (lower,upper,sum)
    calc arr@(hd:_) = go (0,0,hd) (0,hd) 1
    where n = length arr
    go min@(l1,u1,s1) x@(l2,s2) i =
    if i == n then min
    else go min' x' (i+1)
    where arri = arr !! i
    x'@(l2',s2') = if s2 <= 0 then (l2, s2 + arri)
    else (i, arri)
    min' = if s2' < s1 then (l2', i, s2')
    else min

  4. @roy_hu
    虽然我看不懂您的程序,但是您的思路是正确的,《编程珠玑》中也是采用类似的方法,我已经在文中的最后添加了说明。

  5. 貌似代码有问题,全为负数呢?推荐《编程之美》原题以及变体:http://yishan.cc/blogs/nickledson/archive/2008/12/29/997.aspx

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注