题解 | 最大连续子序列

//KY140 最大连续子序列
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int k, a[10005], st[10005], ed[100005];
long long dp[10005];
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    while(cin>>k)
    {
        if(k==0) break;
        bool flag=false;
        for(int i=1;i<=k;i++){
            cin>>a[i];
            if(a[i]>=0) flag=true;
            dp[i]=0;
        }
        if(!flag){
            cout<<0<<' '<<a[1]<<' '<<a[k]<<'\n';
            continue;
        }
        st[0]=1, ed[0]=1;
        for(int i=1;i<=k;i++){
            if(dp[i-1]+a[i]>=a[i]){
                dp[i]=dp[i-1]+a[i];
                ed[i]=i;st[i]=st[i-1];
            }else{
                dp[i]=a[i];
                st[i]=i;
                ed[i]=i;
            }
        }
        long long s=-20000000;
        int l, r;
        for(int i=1;i<=k;i++){
            if(dp[i]>s) {s=dp[i];l=st[i];r=ed[i];}
        }
        cout<<s<<' '<<a[l]<<' '<<a[r]<<'\n';
    }
    return 0;
}