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

最简单、最暴力的算法是枚举法，即一一罗列所有可能的连续子序列，从中找出和值最大的连续子序列，如代码清单1-2所示。maxSubsequenceSum(int a[], int size, int &start, int &end)函数的输入参数为一个待查找的数组a、数组的大小size，输出参数是最大连续子序列的起始位置start、最大连续子序列的终止位置end，返回值为最大连续子序列的和maxSum。程序的主体是一对用来遍历所有可能的连续子序列的循环。循环变量i控制连续子序列的起始位置，循环变量j控制连续子序列的终止位置。对于每个可能的连续子序列，用一个循环变量为k的计数循环计算其和。如果当前连续子序列之和大于目前所遇到的最大连续子序列之和，则更新maxSum、start和end的值。结束循环后，返回maxSum。

代码清单1-2　最大连续子序列和的枚举算法

int maxSubsequenceSum(int a[], int size, int &start, int &end) {
  int maxSum = 0;  // 当前的最大连续子序列之和
　
  for (int i = 0; i < size; i++)  // 子序列的起始位置
    for (int j = i; j < size; j++) {  // 子序列的终止位置
      int thisSum = 0;
      for (int k = i; k <= j; k++)  // 求从i开始到j结束的序列之和
        thisSum+= a[k];
      if (thisSum > maxSum) {  // 找到一个更好的序列
        maxSum = thisSum;
        start = i;
        end = j;
      }
    }
  return maxSum;
}　

这个算法的实现原理非常简单。一个算法越简单，被正确编程的可能性就越大。然而，枚举法通常效率不够高，这个算法的时间复杂度是 O ( n ³ )。

根据求积定理可以看出，这个算法的运行时间完全由循环变量为i的for循环确定。如果输入的序列长度为 n ，则该循环的循环体被运行 n 次。该循环的内层循环体也是一个for循环（循环变量为j的循环），被运行 n − i 次。循环变量为j的for循环是一个复合语句，它由一个赋值语句、一个循环变量为k的循环语句和一个条件语句组成。根据求和定理，该循环体的时间复杂度为循环变量为k的循环语句的时间复杂度。根据规则4，可得代码清单1-2的时间复杂度为 ，属于 O ( n ³ )。

一个有3层嵌套循环的程序，每个循环的运行都有可能处理大部分数组元素，则该程序的时间复杂度为 O ( n ³ )。正是嵌套导致了组合爆炸，为了改进这个算法，需要删除一层循环。 CABYSlFVCRQW/P03SpwqTKg8NgOxJhRpmK4Q9NBjRnany60qYfHSDpaZk4IQnxQi