Maximum Subsequence Sum Problem

• O(\(N^3\)) 「基本思路，逐个列举，略」

• O(\(N^2\)) 「优化一下列举，略」

• divide & conquer O(N logN)

static int
MaxSubSum(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 = MaxSubSum( A, Left, Center ) 
    MaxRightSum = MaxSubSum( A, Center + 1, Right );

    MaxLeftBorderSum = 0; LeftBorderSum = 0;

    for(i=Cente+1;i>=left;i--){
        LeftBorderSum += A[i];
        if(leftBorderSum>MaxleftBorderSum){
            MaxleftBorderSum = LeftBorderSum;
        }
    }

    MaxRightBorderSum = 0; 
    RightBorderSum = 0;
    for(i=Center;i<=Right;i++){
        RightBorderSum += A[i];
        if(RightBorderSum > MaxRightBorderSum){
            MaxRightBOrderSum = RightBorderSum
        }
    }
    return Max(MaxLeftSum,MaxRightSum,MaxLeftBorderSum+MaxRightBorderSum);

}
int MaxsubsequenceSum( const int A[],intN) {
    return MaxSubSum( A, 0, N - 1 );
    }

• 动态规划 O(N)

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

• If counts negative paths

int maxSubArray(int* nums, int numsSize) {
    int pre = 0, maxAns = nums[0];
    for (int i = 0; i < numsSize; i++) {
        pre = fmax(pre + nums[i], nums[i]);
        maxAns = fmax(maxAns, pre);
    }
    return maxAns;
}

---

最后更新: 2024年3月25日 12:53:47
创建日期: 2023年11月2日 09:38:40