K. *【动态规划：区间一维一边推】最大子段和[scy]

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题意】scy240403

给定 $n$ 个数的序列 $a_i$ ，求最大子段和 $S= a_l + a_{l+1} + \dots\ + a_r$ （ $1 \le l \le r \le n$ ）。

【输入格式】

第一行一个整数 $n(1 \le n \le 10^6)$ 。

下来 $n$ 个整数 $a_i(|ai| \le 10^9)$ 。

【输出格式】

一行一个整数，表示最大子段和。

6
-20 11 -4 13 -5 -2