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

#include <iostream>
using namespace std;

const int N = 10010;
int a[N];
int f[N], s[N], e[N];
//f[i]:以第i个数（a[i]）结尾时，最大连续子序列的和
int main() {
    int k;
    while (cin >> k && k) {
        bool flag = false;
        for (int i = 1; i <= k; i++) {
            cin >> a[i];
            if (a[i] >= 0) flag = true;
        }
        if (flag) {
            for (int i = 1; i <= k; i++) {
                f[i] = a[i];
                s[i] = i;
                e[i] = i;
                if (f[i - 1] > 0) {
                    f[i] += f[i - 1];
                    s[i] = s[i - 1];
                }
            }
            int ans = -2 ^ 31, start, end;
            for (int i = 1; i <= k; i++) {
                if (f[i] > ans) {
                    ans = f[i];
                    start = a[s[i]];
                    end = a[i];
                }
            }
            cout << ans << " " << start << " " << end << endl;
        }else{
            cout<<0<<" "<<a[1]<<" "<<a[k]<<endl;
        }

    }
    return 0;
}