题解 | 最大连续子序列

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
int dp[10001];
int s[10001] = {0};
int main() {
    int k;
    bool isMinus = true;
    while (scanf("%d", &k) != EOF) {
        if (k == 0) { break; }
        int num;
        for (int i = 0; i < k; ++i) {
            scanf("%d", &num);
            if (num >= 0) { isMinus = false; }
            s[i] = num;
        }
        if (isMinus) {
            int k = 0;
            while (true) {
                if (s[k] == 0) { break; }
                ++k;
            }
            printf("%d %d %d\n", 0, s[0], s[k - 1]);
            break;
        }
        vector<int> pos;
        int curmax = s[0];
        dp[1] = s[0];
        for (int j = 2; j <= k; ++j) {
            if (dp[j - 1] <= 0) { dp[j] = s[j - 1]; }
            else {
                dp[j] = dp[j - 1] + s[j - 1];
            }
            if (dp[j] > curmax) {
                pos.clear();
                curmax = dp[j];
                pos.push_back(j);
            }
        }
        if (pos.size() != 0) {
            int i = pos[0] - 1;
            int total = s[i];
            while (total != curmax) {
                i = i - 1;
                total += s[i];
            }
            int j = pos[0] - 1;
            printf("%d %d %d\n", curmax, s[i], s[j]);
            pos.clear();
        }
        else {
            printf("%d %d %d\n", curmax, s[0], s[0]);
        }

    }
    return 0;
}