CF1788E Sum Over Zero

给定一个包含 $n$ 个整数的数组 $a_1, a_2, \ldots, a_n$。考虑一个满足以下条件的区间集合 $S$： - $S$ 中的每个元素都应为形如 $[x, y]$ 的区间，其中 $x$ 和 $y$ 是 $1$ 到 $n$ 之间的整数，且 $x \leq y$。 - $S$ 中任意两个区间不能相交。两个区间 $[a, b]$ 和 $[c, d]$ 相交当且仅当存在整数 $x$ 使得 $a \leq x \leq b$ 且 $c \leq x \leq d$。 - 对于 $S$ 中的每个区间 $[x, y]$，都有 $a_x + a_{x+1} + \ldots + a_y \geq 0$。 区间 $[x, y]$ 的长度定义为 $y-x+1$。$f(S)$ 定义为 $S$ 中所有区间长度之和。形式化地，$f(S) = \sum_{[x, y] \in S} (y - x + 1)$。注意，如果 $S$ 为空，则 $f(S) = 0$。 在所有可能的 $S$ 中，最大的 $f(S)$ 是多少？

第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$）。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^9 \leq a_i \leq 10^9$）。

输出一个整数，表示所有可能的 $S$ 中最大的 $f(S)$。

在第一个样例中，$S=\{[1, 2], [4, 5]\}$ 是一个可行的 $S$，因为 $a_1+a_2=0$，$a_4+a_5=1$。$S=\{[1, 4]\}$ 也是一个可行解。 由于不存在 $f(S) > 4$ 的 $S$，所以答案为 $4$。 在第二个样例中，$S=\{[1, 9]\}$ 是唯一满足 $f(S)=9$ 的集合。由于所有可能的 $S$ 都有 $f(S) \leq 9$，所以答案为 $9$。 在第三个样例中，$S$ 只能为空集，所以答案为 $0$。 由 ChatGPT 4.1 翻译