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

#include <iostream>
using namespace std;

//最大序列和（要求输出第一个和最后一个元素）
long long num[1000010];
long long dp[100010];
int first[100010];
int last;

long long maxsubsequence(int n){
    last=0;
    dp[0]=num[0];
    first[0]=0;
    long long ans=dp[0];
    for(int i=1;i<n;i++){
        dp[i]=max(num[i],dp[i-1]+num[i]);
        if(num[i]>dp[i-1]+num[i])first[i]=i;
        else first[i]=first[i-1];
    }
    for(int i=1;i<n;i++)
        if (dp[i]>ans){
            last=i;
            ans=dp[i];
        }
    return ans;
}

int main(){
    int n;
    while(cin>>n){
        if(n==0)break;
        char flag='-';
        for(int i=0;i<n;i++){
            cin>>num[i];
            if(num[i]>=0)flag='+';
        }
        if (flag=='-'){
            cout<<"0 "<<num[0]<<" "<<num[n-1]<<endl;
            continue;
        }
        long long ans=maxsubsequence(n);
        cout<<ans<<" "<<num[first[last]]<<" "<<num[last]<<endl;
    }
    return 0;
}