最大的子序列和问题:给定整数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]重新来计算最大子序列和(来与曾经最美好的最大值来比较,看是现在更好呢,还是之前的更凑合一点)