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

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

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

其实这道题主要考察的是问题转换（或者说是抽象？）的能力，即如何将一个看似复杂的问题转换成一个简单的问题。直接求一个连续子列的和看起来很麻烦，我们要考虑 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(n²)。观察一下数列的规律我们可以发现，如果 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(n²)。所以我觉得仍然不够，不就求一个最小值嘛，为什么那么慢呢，肯定是因为我笨。于是我就在 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章讨论了这个问题¹（只不过是讨论的最大值），在该章最后提出的算法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 对该问题的起源和算法发展做了非常详致的分析。