시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 82 | 39 | 37 | 48.052% |
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.
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$.
5 3 -3 -2 5 -4
4
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.
10 5 -2 -4 -6 2 3 -6 5 3 -2
9
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$.
4 -1 -2 -3 -4
0
In the third example, $S$ can only be an empty set, so the answer is $0$.
Contest > Codeforces > Codeforces Round 851 (Div. 2) E번