Codeforces Round 851 (Div. 2) |
---|
Finished |
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
10 5 -2 -4 -6 2 3 -6 5 3 -2
9
4 -1 -2 -3 -4
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$$$.
Name |
---|