题解 | 最大连续子序列

#include<iostream>
using namespace std;
const int maxn=10000;
int arr[maxn];
int dp[maxn];
int first[maxn];
int last[maxn];
int main(){
    int n;
    while(cin>>n){
        if(n==0){
            break;
        }
        for(int i=0;i<n;i++){
            cin>>arr[i];
        }
        for(int i=0;i<n;i++){
            if(i==0){
                dp[i]=arr[i];
                first[i]=arr[i];
                last[i]=arr[i];
            }
            else{
                if(arr[i]>dp[i-1]+arr[i]){
                    dp[i]=arr[i];
                    first[i]=arr[i];
                    last[i]=arr[i];
                }
                else{
                    dp[i]=arr[i]+dp[i-1];
                    first[i]=first[i-1];
                    last[i]=arr[i];
                }
            }
        }
        int max=dp[0];
        int k=0;
        for(int i=1;i<n;i++){
            if(dp[i]>max){
                max=dp[i];
                k=i;
            }
        }
        if(max<0){
            cout<<"0"<<" "<<arr[0]<<" "<<arr[n-1]<<endl;
        }
        else{
            cout<<max<<" "<<first[k]<<" "<<last[k]<<endl;
        }
    }
}