P3149 - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You’re given an array A. In one move, you can set one of its elements to 0.
Find the minimum number of moves needed to maximize the maximum subarray sum.

EXPLANATION:

If initially A_i \leq 0 for all i, then the maximum subarray sum of A is 0 (by taking the empty subarray, for example), and our moves cannot change that since we’re unable to create positive integers.
So, in this case, the answer is just 0 - we don’t need to perform any moves.

Next, we look at the case when some positive elements exist in A.
Observe that the maximum subarray sum we can obtain is by adding up all the positive elements - and to achieve this, the only way is to ensure that no negative elements are chosen in the subarray.

However, we don’t need to set every negative element to 0: only the ones that are between some positive elements.
For example, if A = [-1, 2, -2, 0, 3], then the first -1 doesn’t need to be set to 0 - we can use just one operation on the -2 to obtain [-1, 2, 0, 0, 3].

So, the solution is as follows:

  • Find L, the index of the leftmost positive element in A.
  • Find R, the index of the rightmost positive element in A.
  • Count the number of negative elements between L and R: that’s the answer.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    if max(a) <= 0: print(0)
    else:
        while a[-1] <= 0: a.pop()
        a = a[::-1]
        while a[-1] <= 0: a.pop()
        ans = 0
        for x in a: ans += x < 0
        print(ans)