题解 | #最大序列和#

#include <stdio.h>

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        int s[n], dp[n];
        for (int i = 0; i < n; i++) {
            scanf("%d", &s[i]);
            dp[i] = s[i];
        }
        long long max_sum = dp[0];
        /*
            for (int i = 1; i < n; i++) {
                if (s[i] < dp[i - 1] + s[i]) {
                    dp[i] = dp[i - 1] + s[i];
                }
                if (dp[i] > max) {
                    max = dp[i];
                }
            }
        */

        for (int i = 1; i < n; i++) {
            // dp[i]为s[i]与dp[i-1]+s[i]中的较大值
            dp[i] = (s[i] > dp[i - 1] + s[i]) ? s[i] : dp[i - 1] + s[i];
            // 更新最大子序列和
            if (dp[i] > max_sum) {
                max_sum = dp[i];
            }
        }
        printf("%lld\n", max_sum);
    }
    return 0;
}