c++——最大子列和

最大子列和问题

//O(N^3)

int MaxSubseqSum1(int A[],int N){

    int ThisSum,MaxSum = ;

    int i,j,k;

    for(i=;i<N;i++){

        for(j=i;j<N;j++)

            ThisSum = ;

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

    int i,j,k;

    for(i=;i<N;i++){

        ThisSum = ;

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

    for(i = ;i<N;i++){

        ThisSum += A[i];

        if(ThisSum>MaxSum)

            MaxSum = ThisSum;

        else if(ThisSum<)

            ThisSum = ;

    }

    return MaxSum;

}

练习题：

#include <stdio.h>

#define MAXN 100000

void MaxSubseqSum(int A[],int N);

int main(){

    int List[MAXN],N,i;

    scanf("%d",&N);

    for (i=;i<N;i++)

        scanf("%d",&List[i]);

    MaxSubseqSum(List,N);

    return ;

}

void MaxSubseqSum(int A[],int N){

    int ThisSum,MaxSum;

    int i,start,end,temp;

    ThisSum = MaxSum = ;

    start = end = temp = ;

    for(i = ;i < N;i++){

        ThisSum += A[i];

        if(ThisSum > MaxSum){

            start = temp;

            end = i;

            MaxSum = ThisSum;

        }

        else if(ThisSum < ){

            temp = i+;

            ThisSum = ;

        }

    }

    if(MaxSum==) end = N-;

    printf("%d %d %d",MaxSum,A[start],A[end]);

}

试点5：负数和0未通过

其他测点通过

#include <stdio.h>

#define MAXN 100000

void MaxSubseqSum(int A[],int N);

int main(){

    int List[MAXN],N,i;

    scanf("%d",&N);

    for (i=;i<N;i++)

        scanf("%d",&List[i]);

    MaxSubseqSum(List,N);

    return ;

}

void MaxSubseqSum(int A[],int N){

    int ThisSum,MaxSum;

    int i,start,end,temp,flag;

    ThisSum = MaxSum = ;

    start = end = temp = flag = ;

    for(i = ;i < N;i++){

        ThisSum += A[i];

        if(A[i]>=) flag = ;

        if(ThisSum > MaxSum){

            start = temp;

            end = i;

            MaxSum = ThisSum;

        }

        else if(ThisSum < ){

            temp = i+;

            ThisSum = ;

        }

    }

    if(MaxSum==){

        if(flag == ){

            printf("0 %d %d",A[],A[N-]);

        }

        else{

            printf("0 0 0");

        }

    }

    else{

        printf("%d %d %d",MaxSum,A[start],A[end]);

    }

}

全部测点通过

这里有个坑，如果全为负数，输出第一个和最后一个元素，如果中间有个0，就要都输出0

还有一个坑就是要输出元素而不是元素下标，题目给的例子元素和下标正好相等，估计会坑不少人