最大子序列之和问题

清疚 2022-08-06 06:06 171阅读 0赞

最大子序列之和问题

这个问题非常有趣，因为有很多中算法可以解决这个问题。而这些算法的执行效率也多种多样。

下面我们将看到四种算法，算法复杂度从指数一直过渡到线性复杂度。

充分体现了算法的优劣对执行效率的影响。

第一种

代码：

int maxSubSum1( const vector<int> & a ) \{

int maxSum = 0;

for ( int i = 0; i < a.size(); i++ )

for ( int j = 1; j < a.size(); j++ ) \{

int thisSum = 0;

for ( int k = i; k <= j; k++ )

thisSum += a\[k\];

if ( thisSum > maxSum )

maxSum = thisSum;

return maxSum;

这个算法很简单，i表示子序列起始下标，j表示子序列结束下标，遍历子序列的开头和结束下标，计算子序列的和，然后判断最大子序列。很明显的看出算法复杂度是O( pow( n, 3 ) )

第二种算法

代码：

int maxSubSum2( const vector<int> & a ) \{

int maxSum = 0;

for ( int i = 0; i < a.size(); i++ ) \{

int thisSum = 0;

for ( int j = i; j <= a.size(); k++ ) \{

thisSum += a\[k\];

if ( thisSum > maxSum )

maxSum = thisSum;

return maxSum;

与第一种很相似，省去了选结束下标的循环语句，算法复杂度是O( pow( n, 2 ) )

第三种

采用了递归的“分而治之”( divide-and-conquer )的思想。

比如 4 -3 5 -2 -1 2 6 -2

First Second

把序列分为两部分，那么最长子序列要么在First，要么在Second，要么就既在First又在Second。

第一中情况只要求First的最大子序列（递归调用），第二中情况只要求Second的最大子序列（还是递归调用）。对于第三种情况，只要找到包含First最后一个元素（在例子中是2）在First的最大子序列（例子中是 4，\-3，5，\-2）和包含Second起始元素（\-1）在Second的最大子序列（\-1，2，6）然后相加就行了。

这种算法的复杂度计算和计算斐波那契数列的复杂度相似，设 N 个数的执行次数是 T( N ) ，那么 T( N ) = 2\*T( N/2 ) + O( N ) 其中T( 1 ) = 1

O( N ) 可以看成 N ，那么可以观察得到 T( N ) = N \* logN

int maxSumRec( const vector<int> & a, int left, int right ) \{

if ( left == right )

if ( a\[ left \] > 0 )

return a\[ left \];

else

return 0;

int center = ( left + right ) / 2;

int maxLeftSum = maxSumRec( a, left, center );

int maxRightSum = maxSumRec( a, center, right );

int maxLeftBorderSum = 0, leftBorderSum = 0;

for ( int i = center; i>= left; i-- ) \{

leftBorderSum += a\[ j \];

if ( leftBorderSum > maxLeftBorderSum )

maxLeftBorderSum = leftBorderSum;

int maxRightBorderSum = 0, RightBorderSum = 0;

for ( int i = center; i <= right; i++ ) \{

RightBorderSum += a\[ j \];

if ( RightBorderSum > maxRightBorderSum )

maxRightBorderSum = rightBorderSum;

return max3( maxLeftSum, maxRightSum, maxLeftSum + maxRightSum ); // 判断三个数最大值的函数

int maxSubSum3( const vector<int> & a ) \{

return maxSumRec( a, 0, a.size() - 1 );

第四种算法

代码：

int maxSubSum( vector<int> & a ) \{

int maxSum = 0, thisSum = 0;

for ( int i = 0; i < a.size(); i++ ) \{

thisSum += a\[i\];

if ( thisSum > maxSum )

maxSum = thisSum;

else if ( thisSum < 0 )

thisSum = 0;

return maxSum;

非常短，而且一眼就看出算法复杂度是O( n )级别的。

我们用i表示子序列的起始下标，j 表示子序列的终止下标。

原理是，当我们得到一个子序列，如果子序列的第一个数是非正数，那么可以舍去，即i++

当一个子序列的前n个元素和为非正数时，是否也可以舍去呢？答案是可以的。

假设k 是i到j中任意一个下标。Sum( a, b ) 表示子序列第a个元素到第b个元素之和。由于加到第j个元素，子序列才开始为负数，所以Sum( i, k ) > 0，Sum( i, k ) + Sum( k, j ) = Sum( i, j ) ,所以Sum( k, j ) < Sum( i, j ) < 0

所以如果把 k到j的序列附加到j之后的序列上，只会使序列越来越小。所以i到j的序列都可以舍去。

这个算法的另外一个优势就是程序是一边读取一边处理数据，a\[ i \] 的值不需要被记住，也就是说不需要把数列的一部分储存在内存中。如果数列是储存在磁盘上，或者是在网络中传播就可以按顺序处理。在任何时候，这个算法都可以根据收到的数据给出结果。有这种特点的算法叫做on-line 算法。