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

#include <iostream>
using namespace std;

const int MAXN = 1e4+10;
int arr[MAXN];
int answer[MAXN];
int Fun(int n){
    int index; //最大值下标
    int maxn = -100000;
    for(int i=0;i<n;i++){
        if(i==0){
            answer[i] = arr[i];
        }else{
            answer[i] = max(arr[i],arr[i]+answer[i-1]);
        }
        if(maxn <answer[i]){
            maxn = answer[i];
            index = i;
        }
    }
    return index;
}
int main() {
    int n;
    while(cin >> n){
        if(n==0){
            break;
        }
        int count = 0;
        for(int i=0;i<n;i++){
            cin>>arr[i];
            if(arr[i]<0){
                count++;
            }
        }
        if(count==n){
            cout<<"0 "<< arr[0]<<" "<<arr[n-1]<<endl;
            continue;
        }
        int index = Fun(n);
        int start = 0;
        int sum = 0;
        for(int i=index;i>=0;i--){
            sum+=arr[i];
            if(sum==answer[index]){
                start = i;
                break;
            }
        }
        cout<<answer[index]<<" "<<arr[start]<<" "<<arr[index]<<endl;
    }

}