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

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;
}

return max3(maxLeftSum,maxRightSum,
maxLeftBorderSum+ maxRightBorderSum);
}

long maxSubSum3(const vector&a)
{
return maxSumRec(a,0, a.size()-1);
}
另外max3(long,long,long)表示求三个long中的最大值：
//求出三个long中的最大值
long max3(long a, long b, long c)
{
if (a< b)
{
a= b;
}
if (a> c)
return a;
else
return c;
}

对这个算法进行分析：

T(1) = 1

T(N) = 2T(N/2) +O(N)

最后得出算法的复杂度为：O(NlogN) 。

算法四：

下面介绍一个线性的算法，这个算法是许多聪明算法的典型：运行时间是明显的，但是正确性则很不明显（不容易理解）。

//线性的算法O(N)

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

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

很容易理解时间界O(N) 是正确的，但是要是弄明白为什么正确就比较费力了。其实这个是算法二的一个改进。分析的时候也是i代表当前序列的起点，j代表当前序列的终点。如果我们不需要知道最佳子序列的位置，那么i就可以优化掉。

重点的一个思想是：如果a[i]是负数那么它不可能代表最有序列的起点，因为任何包含a[i]的作为起点的子序列都可以通过用a[i+1]作为起点来改进。类似的有，任何的负的子序列不可能是最优子序列的前缀。例如说，循环中我们检测到从a[i]到a[j]的子序列是负数，那么我们就可以推进i。关键的结论是我们不仅可以把i推进到i+1，而且我们实际可以把它一直推进到j+1。

举例来说，令p是i+1到j之间的任何一个下标，由于前面假设了a[i]+…+a[j]是负数，则开始于下标p的任意子序列都不会大于在下标i并且包含从a[i]到a[p-1]的子序列对应的子序列（j是使得从下标i开始成为负数的第一个下标）。因此，把i推进到j+1是安全的，不会错过最优解。注意的是：虽然，如果有以a[j]结尾的某序列和是负数就表明了这个序列中的任何一个数不可能是与a[j]后面的数形成的最大子序列的开头，但是并不表明a[j]前面的某个序列就不是最大序列，也就是说不能确定最大子序列在a[j]前还是a[j]后，即最大子序列位置不能求出。但是能确保maxSum的值是当前最大的子序列和。这个算法还有一个有点就是，它只对数据进行一次扫描，一旦a[j]被读入处理就不需要再记忆。它是一个联机算法。联机算法：在任意时刻算法都能够对它已读入的数据给出当前数据的解。