最大子序列和问题的解

最大的子序列和问题:给定整数A1,A2,......,AN(可能有负数),求∑Ak(k=i...j)的最大值。(为方便起见,如果所有整数均为负数,则最大子序列和为0)

例:输入-2,11,-4,13,-5,-2时,答案为20(从A2到A4)

解法一:

int MaxSubsequenceSum( const int A[], int N )
{
	int ThisSum, MaxSum, i, j, k;
	
	MaxSum = 0;
	for ( i = 0; i < N; i++ ) {
		for ( j = i; j < N; j++ ) {
			ThisSum = 0;
			for ( k = i; k <= j; k++ ) {
				ThisSum += A[k];
			}
			
			if ( ThisSum > MaxSum ) {
				MaxSum = ThisSum;
			}
		}
	}
	
	return MaxSum;
}
相当于列举出从A0到An中所有可能组合中最大的Sum。时间复杂度为O(N^3)


解法二:

解法一中在求MaxSum时,最内层的for循环可以改写,降低时间复杂度。有如下解法:


int MaxSubsequenceSum( const int A[], int N )
{
	int ThisSum, MaxSum, i, j, k;
	
	MaxSum = 0;
	for ( i = 0; i < N; i++ ) {
		for ( j = i; j < N; j++ ) {
			ThisSum = 0;
			ThisSum += A[j];
			
			if ( ThisSum > MaxSum ) {
				MaxSum = ThisSum;
			}
		}
	}
	
	return MaxSum;
}

明显时间复杂度为O(N^2)


解法三:

解法三利用到分治的思想:其想法是把问题分成两个大致相等的子问题,然后递归地对它们求解,这是“分”部分。“治”阶段将两个子问题的解合并到一起并可能再做些少量附加工作。

从A[]的中间分开,明显最大子序列可能出现在前一半或后一半,或前一半后部分+后一半的前部分。

而这又可以递归下去。由此有解法三:


int MaxSubSum( const int A[], int Left, int Right ) 
{
	int MaxLeftSum, MaxRightSum; //左半部分的最大子序列和, 右半部分的最大子序列和
	int MaxLeftBorderSum, MaxRightBorderSum; //左半部分倒着数的最大子序列和, 有半部分倒着数的最大子序列和(分别都包括靠近中间center的元素)
	int TmpLeftBorderSum, TmpRightBorderSum; //计算MaxLeftBorderSum, MaxRightBorderSum用到的临时求解最大子序列和的变量
	int center, i;
	
	if ( Left == Right ) { //基准情况
		if ( A[Left] > 0 ) {
			return A[Left];
		}
		else {
			return 0;
		}
	}
	
	center = ( Left + Right ) / 2;
	MaxLeftSum = MaxSubSum( A, Left, center );
	MaxRightSum = MaxSubSum( A, center + 1, Right );
	
	MaxLeftBorderSum = 0, TmpLeftBorderSum = 0;
	for ( i = center; i >= Left; i-- ) { //左半部分倒着数的最大子序列和
		TmpLeftBorderSum += A[i];
		if ( TmpLeftBorderSum > MaxLeftBorderSum ) {
			MaxLeftBorderSum = TmpLeftBorderSum;
		}
	}
	
	MaxRightBorderSum = 0, TmpRightBorderSum = 0;
	for ( i = center + 1; i <= Right; i++ ) { //有半部分倒着数的最大子序列和
		TmpRightBorderSum += A[i];
		if ( TmpRightBorderSum > MaxRightBorderSum ) {
			MaxRightBorderSum = TmpRightBorderSum;
		}
	}
	
	return Max3( MaxLeftSum, MaxRight, MaxLeftBorderSum + MaxRightBorderSum );
}

int MaxSubsequenceSum( const int A[], int N )
{
	return MaxSubSum( A, 0, N - 1 );
}
O(NlogN)时间复杂度


解法四:

int MaxSubsequenceSum( const int A[], int N )
{
	int ThisSum, MaxSum, i;
	
	ThisSum = 0, MaxSum = 0;
	for ( i = 0; i < N; i++ ) {
		ThisSum += A[i];
		
		if ( ThisSum > MaxSum ) {
			MaxSum = ThisSum;
		}
		else if ( ThisSum < 0 ) {
			ThisSum = 0;
		}
	}
	
	return MaxSum;
}

解法四时间复杂度仅为O(n),但不是很好理解。

else if那里既ThisSum加上A[i]之后值反而比没加之前还小,而且小到A[i]竟然不起正作用,还起了反作用(既使包括A[i]),这样我们就应该把这段并不美好的经历忘记,从A[i+1]重新来计算最大子序列和(来与曾经最美好的最大值来比较,看是现在更好呢,还是之前的更凑合一点)

;