题解 | #最大序列和#

#include<cstdio>
#include<iostream>
#include<climits>
using namespace std;
#define N 1000000
long long a[N + 1];
long long dp[N + 1];
long long maxsub(int n) {
    long long maximun = -INT_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]);
        }
        maximun =  max(maximun, dp[i]);
    }
    return  maximun;
}
int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        for (int i = 0 ; i < n ; ++i) {
            scanf("%lld", &a[i]);
        }
        long long answer = maxsub(n);
        printf("%lld\n", answer);
    }
}