Zhily and Array Operating

Observation 1: ask a simpler question

Instead of directly maximizing the number of positive elements, first ask:

What is the maximum value each position can possibly become?

Let $mx_i$ be the maximum final value that index $i$ can obtain if we are allowed to perform any valid operations on the suffix $i,i+1,\dots,n$.

For the last element, nothing can affect it: $mx_n=a_n.$

Now look at some index $i<n$.

There are only two sane options:

• Do not use operation $i$ at all. Then the final value is just $a_i$.
• Use operation $i$ once. Then you add the current value of $a_{i+1}$.

If you want to maximize index $i$, then obviously you should apply operation $i$ when index $i+1$ is as large as possible. That best possible value is exactly $mx_{i+1}$.

So: $mx_i=\max(a_i,\ a_i+mx_{i+1}).$ Which is the same as: $mx_i=a_i+\max(0,mx_{i+1}).$

That recurrence is the whole problem. Everything else is just paperwork.

---

Observation 2: negative help is not help

If $mx_{i+1}>0$, then adding it to $a_i$ is strictly better than ignoring it.

If $mx_{i+1}\le 0$, then adding it is useless or harmful, so the best choice is to skip operation $i$.

So while scanning from right to left:

• if the optimized value on the right is positive, absorb it;
• otherwise, leave the current element alone.

This is basically: take free money, refuse debt. Revolutionary stuff.

---

Observation 3: why counting positive $mx_i$ is the answer

Upper bound

If $mx_i\le 0$, then even the best possible final value of index $i$ is non-positive. So in any valid final array, position $i$ cannot be positive.

Therefore the answer is at most: $\#\{i \mid mx_i>0\}.$

Lower bound / achievability

Now the nice part: the array $mx$ itself is achievable.

Process indices from right to left. At step $i$:

• index $i+1$ has already been fixed to value $mx_{i+1}$;
• if $mx_{i+1}>0$, perform operation $i$, so $a_i \gets a_i+mx_{i+1}=mx_i;$
• otherwise skip it, so $a_i=mx_i=a_i.$

This never changes positions to the right, so the construction is valid. Hence we can make every index with $mx_i>0$ positive simultaneously.

So the answer is exactly: $\#\{i \mid mx_i>0\}.$

---

Algorithm

For each test case:

1. Set $cur=a_n$.
2. Initialize answer with whether $cur>0$.
3. For $i=n-1,n-2,\dots,1$:
   • update $cur=a_i+\max(0,cur);$
   • if $cur>0$, increment the answer.

Here $cur$ is just the current $mx_i$ while moving left.

---

Correctness sketch

We proved:

1. $mx_n=a_n,$ and for $i<n$, $mx_i=a_i+\max(0,mx_{i+1}).$
2. No final value at position $i$ can exceed $mx_i$, so if $mx_i\le 0$, index $i$ can never be positive.
3. The right-to-left construction realizes final values exactly equal to $mx_i$.

Therefore the maximum possible number of positive elements is exactly the number of positive values among the $mx_i$.

Done. No black magic, no cursed DP state explosion, just a very polite backward sweep.

---

Complexity

Each test case is processed in one pass from right to left.

• Time: $O(n)$
• Memory: $O(1)$ extra

Over all test cases, this is $O\left(\sum n\right)$, which easily fits the limits.