题解 | #最大序列和#

#include <iostream>

using namespace std;

long long a[1000001];
long long dp[1000001];

long long maxsubsequence(int n) {
    long long maxinum = -INT32_MAX;
    for (int i = 0; i < n; i++) {
        if (i == 0) {
            dp[i] = a[i];  //只有一个元素，必然是最大连续子序列
        } else {
            dp[i] = max(a[i], a[i] + dp[i - 1]);
        }
        if (dp[i] > maxinum) {
            maxinum = dp[i];
        }
    }
    return maxinum;
}

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        for (int i = 0; i < n; i++) {
            scanf("%lld", &a[i]);
        }
        long long ans = maxsubsequence(n);
        printf("%lld\n", ans);

    }
    return 0;
}