求最大连续子序列和问题 (一)

问题描述：

输入一组整数，求出这组数字子序列和中最大值。也就是只要求出最大子序列的和，不必求出最大的那个序列。例如：

序列：-2 11 -4 13 -5 -2，则最大子序列和为20。

序列：-6 2 4 -7 5 3 2 -1 6 -9 10 -2，则最大子序列和为16。

算法一：

//穷举法，复杂度O(n^3) 最容易想到也是最简单的算法

[cpp]
long maxSubSum1(const vector&a)
{
long maxSum= 0;
for (int i= 0; i < a.size(); i++)
{
for (int j= i; j < a.size(); j++)
{
long thisSum= 0;

for (int k= i; k <= j; k++)
{
thisSum+= a[k];
}
if (thisSum> maxSum)
maxSum= thisSum;
}
}
return maxSum;
}

long maxSubSum1(const vector&a)
{
long maxSum= 0;
for (int i= 0; i < a.size(); i++)
{
for (int j= i; j < a.size(); j++)
{
long thisSum= 0;

for (int k= i; k <= j; k++)
{
thisSum+= a[k];
}
if (thisSum> maxSum)
maxSum= thisSum;
}
}
return maxSum;
}

这是一个O(N^3) 的算法，算法本身很容易理解，而且很直观的感觉做了很多无用操作。例如：i = 0, j = 3时，会计算a[0] +a[1] +…+ a[3]；而当i = 0, j = 4时候又会计算a[0]+ a[1] +…a[4]。

算法二：

通过撤出一个for循环来避免三次时间。

//也是穷举法，不过减去了上面的一些不必要操作O(n^2)

[cpp]
long maxSubSum2(const vector&a)
{
long maxSum= 0;
for (int i= 0; i < a.size(); i++)
{
long thisSum= 0;
for (int j= i; j < a.size(); j++)
{
thisSum+= a[j];
if (thisSum> maxSum)
maxSum= thisSum;
}
}
return maxSum;
}

long maxSubSum2(const vector&a)
{
long maxSum= 0;
for (int i= 0; i < a.size(); i++)
{
long thisSum= 0;
for (int j= i; j < a.size(); j++)
{
thisSum+= a[j];
if (thisSum> maxSum)
maxSum= thisSum;
}
}
return maxSum;
}

这是一个非常直观的穷举法（比上面的分析还有简单些），而且没有多余重复的操作，复杂度为O(N^2) 。其中，thisSum表示a[i] + a[i+1] + … + a[j-1]。

算法三：

对这个问题，有一个相对复杂的O(NlogN)的解法，就是使用递归。如果要是求出序列的位置的话，这将是最好的算法了（因为我们后面还会有个O(N)的算法，但是不能求出最大子序列的位置）。该方法我们采用“分治策略”（divide-and-conquer）。

在我们例子中，最大子序列可能在三个地方出现，或者在左半部，或者在右半部，或者跨越输入数据的中部而占据左右两部分。前两种情况递归求解，第三种情况的最大和可以通过求出前半部分最大和（包含前半部分最后一个元素）以及后半部分最大和（包含后半部分的第一个元素）相加而得到。

//递归法，复杂度是O(nlogn)

[cpp]
long maxSumRec(const vector&a, int left, int right)
{
if (left== right)
{
if (a[left]> 0)
return a[left];
else
return 0;
}
int center= (left + right) / 2;
long maxLeftSum= maxSumRec(a, left, center);
long maxRightSum= maxSumRec(a, center+1, right);

//求出以左边对后一个数字结尾的序列最大值
long maxLeftBorderSum= 0, leftBorderSum = 0;
for (int i= center; i >= left; i--)
{
leftBorderSum+= a[i];
if (leftBorderSum> maxLeftBorderSum)
maxLeftBorderSum= leftBorderSum;
}

//求出以右边对后一个数字结尾的序列最大值
long maxRightBorderSum= 0, rightBorderSum = 0;
for (int j= center+1; j <= right; j++)
{
rightBorderSum+= a[j];
if (rightBorderSum> maxRightBorderSum)
maxRightBorderSum= rightBorderSum;
}