题解 | #最大连续子序列#

简单DP

思路：统计以s[i]结尾的最大子序列和ans[i],多递推一个起始下标即可

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int maxn=10001;
long long s[maxn];//序列
long long ans[maxn];//以s[i]结尾的最大子序列和

void maxsequence(int n){
    long long maxans=-1;//最大子序列和
    int index;//最大子序列的结束下标
    
    int first[n];//最大子序列的起始下标
   
    for(int i=0;i<n;i++){
        if(i==0) {
            ans[i]=s[i];//起始
            first[i]=i;
        }
        else{
            if(s[i]+ans[i-1]>=s[i]){
                ans[i]=s[i]+ans[i-1];
                first[i]=first[i-1];
            }
            else {
                ans[i]=s[i];
                first[i]=i;
            }    
        }//递推
        
        if(ans[i]>maxans){
            maxans=ans[i];
            index=i;
        };//更新最大子序列和、结束下标
    }
    if(maxans==-1){//都是负数
        maxans=0;
        index=n-1;
        first[index]=0;
    }
    printf("%d %d %d\n",maxans,s[first[index]],s[index]);
}

int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        if(n==0)break;
        for(int i=0;i<n;i++)scanf("%lld",&s[i]);
        maxsequence(n);
    }
    return 0;
}