动手学数据结构与算法最新章节_俞勇著

1.4.4 时间复杂度为 O ( n )的算法

最大连续子序列和：改进算法 O ( n )

最大连续子序列和问题的算法还可以继续优化。进一步观察代码清单1-3所示的两重循环算法，如果能再删除一个循环，就可以得到一个线性算法。然而，从代码清单1-2到代码清单1-3删除循环很简单，但要再删除另一个循环就不那么容易了。这个问题的关键在于平方级算法仍然是一种枚举法，也就是说，还是尝试了所有可能的子序列。平方级算法和立方级算法唯一的不同就是计算每个最大连续子序列和的时间复杂度是常量 O (1)而不是线性的 O ( n )。因为序列具有平方数目的连续子序列数，所以得到一个线性算法的唯一方法就是找出一个聪明的方法排除对很多连续子序列的考虑，而不用真正计算所有连续子序列的和值。

我们可以通过分析来排除很多可能的连续子序列。如果一个连续子序列的和是负的，则它不可能是最大连续子序列的开始部分，因为可以通过不包含它得到一个连续子序列和值更大的连续子序列。例如，{−2,11,−4,13,−5,2}的最大连续子序列不可能从−2开始，{1,−3,4,−2,−1,6}的最大连续子序列不可能包含{1,−3}。所有与最大连续子序列毗邻的连续子序列一定有负的和值或0和值。因此，在代码清单1-5中，当检测出一个负的连续子序列和时，不但可以从内层循环中跳出来，还可以让i直接增加到j+1。例如，对于{1,−3,4,−2,−1,6}，当检测序列{1,−3}后，发现连续子序列和是负值，则该子序列不可能包含在最大连续子序列中，接下来i就可以从4开始检测。使用这种方法，只需要顺序检查一遍序列中的元素。根据该思想实现的算法如代码清单1-5所示。

代码清单1-5　最大连续子序列和的线性算法

int maxSubsequenceSum(int a[], int size, int &start, int &end) {
  int maxSum, starttmp, thisSum;
  start = end = maxSum = starttmp = thisSum = 0;
  for (int j = 0; j < size;++j) {
    thisSum+= a[j];
    if (thisSum <= 0) {  // 排除前面的连续子序列
      thisSum = 0;
      starttmp = j+1;
    } else if (thisSum > maxSum) {  // 找到一个连续子序列和更大的连续子序列
      maxSum = thisSum;
      start = starttmp;
      end = j;
    }
  }
  return maxSum;
}

代码清单1-5只使用了一个最多重复 n 次的循环，显然这个算法的运行时间是线性的。这个循环体最多重复运行 n 次，而循环体中语句的运行次数是常数级的，与问题规模无关。因此时间复杂度是 O ( n )。但与前面几个算法相比，这个算法读起来不那么方便，也就是说，牺牲了易读性换取了时间！