Codeforces B - Just Eat It!

分析

• 一眼看出判断连续子序列最大和（贪心），但练习 $dp$ 。
• $d{p}_i$ 表示以 $a_i$ 结尾的最大连续子序列之和。
• $d{p}_i=\{\begin{array}{l}d{p}_i+d{p}_{i?1}ifd{p}_{i?1}>0\\ d{p}_{i}else\end{array}$ 。

Think Twice, Code once

signed main() {

    int T = 1;
    T = read();
    while (T--) {
        int n = read();
        vector<int> dp(n + 1), cnt(n + 1, 1);
        int sum = 0;
        bool f = 1;
        for (int i = 1; i <= n; ++i) {
            sum += dp[i] = read();
            if (dp[i] < dp[i] + dp[i - 1]) {
                dp[i] += dp[i - 1];
                cnt[i] += cnt[i - 1];
            }
        }
        for (int i = 1; i < n; ++i) {
            if (sum <= dp[i]) {
                f = 0;
                break;
            }
        }
        if (sum <= dp[n] && cnt[n] ^ n) f = 0;
        f? puts("YES"): puts("NO");
    }
    return 0;
}