题解 | 最大连续子序列

#include<iostream>


using namespace std;
const int maxn = 10005;
int dp[maxn];
int a[maxn];
int main() {
    int n;
    while (cin >> n) {
        if (n == 0)break;
        int flag = 1;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            if (a[i] >= 0)flag = 0;
        }
        if (flag == 1) { //全为负
            cout << 0 << " " << a[0] << " " << a[n - 1] << endl;
            continue;
        }
        dp[0] = a[0];
        int maxd = dp[0], lhs = 0, rhs = 0, flagl = 0, flagr = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] > dp[i - 1] + a[i]) {
                dp[i] = a[i];
                flagl = i;
                flagr = i;
            } else {
                dp[i] = dp[i - 1] + a[i];
                flagr = i;
            }
            if (maxd < dp[i]) {
                maxd = dp[i];
                lhs = flagl;
                rhs = flagr;
            }
        }
        cout << maxd << " " << a[lhs] << " " << a[rhs] << endl;
    }
}