题解 | 最大连续子序列

#include <iostream>

using namespace std;
#define N 10010
int a[N];
int n;

bool check() {  // 判断序列是否全为<0
    bool flag = true;
    for (int i = 1; i <= n; ++i) {
        if (a[i] >= 0)
            flag = false;
    }
    return flag;
}

void getMaxSubseqSum() {
    int cur_max = -1e8;
    int res = -1e8;
    int curl = -1;  // 当前最大子序列和的最左边元素下标
    int curr = -1;  // 当前最大子序列和的最右边元素下标
    int maxl = -1;  // 全局最大子序列和的最左边元素下标
    int maxr = -1;  // 全局最大子序列和的最右边元素下标
    for (int i = 1; i <= n; ++i) {
        if (a[i] > a[i] + cur_max) {
            curl = curr = i;
            cur_max = a[i];
        } else {
            cur_max = a[i] + cur_max;
            curr = i;
        }
        if (cur_max > res) {
            maxl = curl;
            maxr = curr;
            res = cur_max;
        }
    }
    printf("%d %d %d\n", res, a[maxl], a[maxr]);
}
int main() {
    while (scanf("%d", &n) != EOF && n > 0) {
        for (int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        if (check()) {
            printf("%d %d %d\n", 0, a[1], a[n]);
            continue;
        }
        getMaxSubseqSum();
    }

    return 0;
}