xht37 的洛谷博客

xht37's blog:https://www.xht37.com/

题解 CF1326B 【Maximums】

依照题意,我们可以得到一个递推式 $a_n = \max_{i=1}^{n-1} a_i + b_n$,时间复杂度 $\mathcal O(n)$。

const int N = 2e5 + 7;
int n;
ll a[N], x;

int main() {
    rd(n), rda(a, n);
    for (int i = 1; i <= n; i++)
        print(x + a[i], " \n"[i==n]), x = max(x, x + a[i]); 
    return 0;
}

2020-03-21 04:40:26 in 题解