题解 | #最大序列和#

#include <climits>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// 可以dp，也可以贪心
int main() {
    int n;
    while (cin >> n) {
        vector<long long> f(n);
        long long ans = INT_MIN, t = 0;
        for (int i = 0; i < n; i++) cin >> f[i];
        vector<long long> dp(n + 1, INT_MIN / 2); // dp[i]表示以f[i]结尾的最大成果
        // dp[i + 1] = max(dp[i] + f[i], f[i])
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            dp[i + 1] = max(dp[i] + f[i], f[i]);
        }

        cout << *max_element(dp.begin() + 1, dp.end()) << endl;
    }
}