# 最大子序列和问题的解

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

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

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

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

;