c++——最大子列和

//O(N^3)
int MaxSubseqSum1(int A[],int N){
    int ThisSum,MaxSum = 0;
    int i,j,k;
    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 MaxSubseqSum2(int A[],int N){
    int ThisSum,MaxSum = 0;
    int i,j,k;
    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(N*logN)——分治 

//O(N)——在线处理 
int MaxSubseqSum4(int A[],int N){
    int ThisSum,MaxSum;
    int 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;
}