寻找数组中的最大子向量和

编程珠玑里讲到如何以最快的速度求数组中的最大子向量和（数组里包括了负数）。

 

如果采用一般的遍历所有的可能的情况可能的复杂度是O(n^3)或O(n^2)，主要是中间会重复计算了一些数。最快的方法就是只扫描一遍就可以求出结果，时间复杂度是O(n)。

 

方法是采用两个变量分别保存当前的子向量和最大值max_sofar、以及加上当前数组元素的子向量和的最大值max_ending。当max_ending为负数时就重置为0，接着重新计算子向量和。

 

源码实现如下：

 

#include
#include

#define N 8

int max_sub_sum(const int *x, const int n);
int max(int a, int b);

int main()
{
 const int x[N] = { -2, 7, 1, -6, -2, 9, 2, -1 };
 
 int result = max_sub_sum(x, N);

 printf("Result: %d\n", result);

 return 0;
}

int max_sub_sum(const int *x, const int n)
{
 int max_sofar = 0;
 int max_ending = 0;

 for (int i = 0; i < n; ++i)
 {
  max_ending = max(max_ending + x[i], 0);
  max_sofar = max(max_sofar, max_ending);
 }

 return max_sofar;
}

int max(int a, int b)
{
 return (a > b) ? a : b;
}