Sum Over Zero

题意翻译

给你一个长度为 $n$ 的序列 $a_1,a_2 ... a_{n-1},a_n$，现在请你找到这个序列的若干个**不相交的合法子段**。 对于你选择的一个子段 $[x,y]$，其为一个合法子段当且仅当 $\sum^{i\leq y}_{i=x} a_i \geq 0$，即子段的区间和非负。 对于一个合法的子段 $S=[x,y]$，我们记 $f(S)=(y-x+1)$，且当子段 $S$ 为空时， $f(S)=0$。 对于你选择的这若干个**不相交合法子段**，请最大化$\sum_S f(S)$并输出这个最大值

题目描述

You are given an array $ a_1, a_2, \ldots, a_n $ of $ n $ integers. Consider $ S $ as a set of segments satisfying the following conditions. - Each element of $ S $ should be in form $ [x, y] $ , where $ x $ and $ y $ are integers between $ 1 $ and $ n $ , inclusive, and $ x \leq y $ . - No two segments in $ S $ intersect with each other. Two segments $ [a, b] $ and $ [c, d] $ intersect if and only if there exists an integer $ x $ such that $ a \leq x \leq b $ and $ c \leq x \leq d $ . - For each $ [x, y] $ in $ S $ , $ a_x+a_{x+1}+ \ldots +a_y \geq 0 $ . The length of the segment $ [x, y] $ is defined as $ y-x+1 $ . $ f(S) $ is defined as the sum of the lengths of every element in $ S $ . In a formal way, $ f(S) = \sum_{[x, y] \in S} (y - x + 1) $ . Note that if $ S $ is empty, $ f(S) $ is $ 0 $ . What is the maximum $ f(S) $ among all possible $ S $ ?

输入输出格式

输入格式

The first line contains one integer $ n $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ). The next line is followed by $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ -10^9 \leq a_i \leq 10^9 $ ).

输出格式

Print a single integer, the maximum $ f(S) $ among every possible $ S $ .

输入输出样例

输入样例 #1

5
3 -3 -2 5 -4

输出样例 #1

4

输入样例 #2

10
5 -2 -4 -6 2 3 -6 5 3 -2

输出样例 #2

9

输入样例 #3

4
-1 -2 -3 -4

输出样例 #3

0

说明

In the first example, $ S=\{[1, 2], [4, 5]\} $ can be a possible $ S $ because $ a_1+a_2=0 $ and $ a_4+a_5=1 $ . $ S=\{[1, 4]\} $ can also be a possible solution. Since there does not exist any $ S $ that satisfies $ f(S) > 4 $ , the answer is $ 4 $ . In the second example, $ S=\{[1, 9]\} $ is the only set that satisfies $ f(S)=9 $ . Since every possible $ S $ satisfies $ f(S) \leq 9 $ , the answer is $ 9 $ . In the third example, $ S $ can only be an empty set, so the answer is $ 0 $ .

**题目大意：**
给定一个长度为 $ n $ 的整数序列 $ a_1, a_2, \ldots, a_n $，需要找出若干个**互不相交的合法子段**。一个子段 $[x, y]$ 是合法的当且仅当这个子段内所有数的和大于或等于 0，即 $\sum_{i=x}^{y} a_i \geq 0$。对于每个合法子段 $S=[x, y]$，定义 $f(S) = y - x + 1$ 为子段的长度，如果子段为空，则 $f(S) = 0$。需要最大化所有选择的合法子段长度的总和 $\sum_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) $ 的最大值。

**输入输出样例：**
- **输入样例 #1：**
```
5
3 -3 -2 5 -4
```
- **输出样例 #1：**
```
4
```
- **输入样例 #2：**
```
10
5 -2 -4 -6 2 3 -6 5 3 -2
```
- **输出样例 #2：**
```
9
```
- **输入样例 #3：**
```
4
-1 -2 -3 -4
```
- **输出样例 #3：**
```
0
```**题目大意：** 给定一个长度为 $ n $ 的整数序列 $ a_1, a_2, \ldots, a_n $，需要找出若干个**互不相交的合法子段**。一个子段 $[x, y]$ 是合法的当且仅当这个子段内所有数的和大于或等于 0，即 $\sum_{i=x}^{y} a_i \geq 0$。对于每个合法子段 $S=[x, y]$，定义 $f(S) = y - x + 1$ 为子段的长度，如果子段为空，则 $f(S) = 0$。需要最大化所有选择的合法子段长度的总和 $\sum_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) $ 的最大值。 **输入输出样例：** - **输入样例 #1：** ``` 5 3 -3 -2 5 -4 ``` - **输出样例 #1：** ``` 4 ``` - **输入样例 #2：** ``` 10 5 -2 -4 -6 2 3 -6 5 3 -2 ``` - **输出样例 #2：** ``` 9 ``` - **输入样例 #3：** ``` 4 -1 -2 -3 -4 ``` - **输出样例 #3：** ``` 0 ```