首页 > 编程语言 > 详细

c++——最大子列和

时间:2019-03-27 20:44:54      阅读:129      评论:0      收藏:0      [点我收藏+]

最大子列和问题

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

 

c++——最大子列和

原文:https://www.cnblogs.com/cxc1357/p/10610243.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!