吉吉于

Max Subsequence Sum Problem

The maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers (containing at least one positive number) which has the largest sum.

O(N^3)

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

O(N^2)

int
MaxSubsequenceSum(const int A[], int N){
    int ThisSum, MaxSum, i, j;

    MaxSum = 0;
    for (i=0; i<N; i++){
        ThisSum = 0;
        for (j=i; j<N; j++){
            ThisSum += A[j];

            if (ThisSum > MaxSum){
                MaxSum = ThisSum;
            }
        }
    }
    return MaxSum;
}

O(NlogN)

int
MaxSubsequenceSum(const int A[], int Left, int Right){
    int MaxLeftSum, MaxRightSum;
    int MaxLeftBorderSum, MaxRightBorderSum;
    int LeftBorderSum, RightBorderSum;
    int Center, i;

    if (Left == Right){
        if (A[Left] > 0){
            return A[Left];
        } else {
            return 0;
        }
    }

    Center = (Left + Right) / 2;
    MaxLeftSum = MaxSubsequenceSum(A, Left, Center);
    MaxRightSum = MaxSubsequenceSum(A, Center+1, Right);

    MaxLeftBorderSum = 0; LeftBorderSum = 0;
    for (i=Center; i>=Left; i--){
        LeftBorderSum += A[i];
        if (LeftBorderSum > MaxLeftBorderSum){
            MaxLeftBorderSum = LeftBorderSum;
        }
    }

    MaxRightBorderSum = 0; RightBorderSum = 0;
    for (i=Center+1; i<=Right; i++){
        RightBorderSum += A[i];
        if (RightBorderSum > MaxRightBorderSum){
            MaxRightBorderSum = RightBorderSum;
        }
    }

    return MAX(MAX(MaxLeftSum, MaxRightSum), MaxLeftBorderSum + MaxRightBorderSum);
}

O(N)

int
MaxSubsequenceSum(const int A[], int N){
    int ThisSum, MaxSum, i;

    ThisSum = MaxSum = 0;
    for (i=0; i<N; i++){
        ThisSum += A[i];

        if (ThisSum > MaxSum){
            MaxSum = ThisSum;
        } else if(ThisSum < 0){
            ThisSum = 0;
        }
    }
    return MaxSum;
}

Reference:

Data Structures and Algorithm Analysis in C (2nd Edition) Chapter2