Sum Over Zero
Contest: Codeforces Round 851 (Div. 2)
Difficulty rating: 2200
Tags: data structures, dfs and similar, dp

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$$$?

Input format:
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$$$).

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

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
5
3 -3 -2 5 -4

Example output:
4

Example input:
10
5 -2 -4 -6 2 3 -6 5 3 -2

Example output:
9

Editorial:
Denote $$$p$$$ as the prefix sum of $$$a$$$. For a segment $$$[x+1, y]$$$ to be an element of $$$S$$$, $$$p_x \leq p_y$$$ should be satisfied.
Let's denote $$$dp_i$$$ as the maximum value of the sum of length of segment smaller than $$$i$$$ in $$$S$$$. Segment $$$[x, y]$$$ is smaller than $$$i$$$ if $$$y \leq i$$$. If there is no segment ending at $$$i$$$, $$$dp_i=dp_{i-1}$$$. If there is segment $$$[k+1, i]$$$ in $$$S$$$, $$$dp_i=\max_{ p_{k} \leq p_i }(dp_k+i-k)$$$. By summing up, $$$dp_i = \max(dp_{i-1}, \max_{p_k \leq p_i}(dp_k+i-k)$$$ With this dp, we get an $$$O(N^2)$$$ solution.
Now let's try to speed up the dp transition using segment tree. First, use coordinate compression on $$$p_i$$$ since we only see whether one prefix sum is bigger than the other. We will maintain a segment tree that stores $$$dp_k-k$$$ in position $$$p_k$$$.
Let's find $$$dp_i$$$ in order of $$$i$$$. $$$dp_i = \max(dp_{i-1}, \max_{p_k \leq p_i}(dp_k-k)+i)$$$ We can solve $$$\max_{p_k \leq p_i}(dp_k-k)$$$ by range query $$$[0, p_i]$$$ on a segment tree. So we can solve $$$dp_i$$$ in $$$O(logN)$$$ for each $$$i$$$.
The entire problem is solved in $$$O(NlogN)$$$.
There is an alternative solution that maintains pair $$$(dp_k-k, p_k)$$$ monotonically with a set. This solution also runs in $$$O(NlogN)$$$.