FastPrepFastPrep
Problem Brief

Maximize Negative Signs

OA
See Amazon online assessment and hiring insights

Given a sequence of n natural numbers a_1, a_2, ..., a_n, you are to assign a sign (+ or -) to each a_i such that the cumulative sum of the signed a_1 + a_2 + ... + a_i remains positive for each i in 1 <= i <= n. Your task is to maximize the number of assigned negative signs, while still satisfying the above condition.

Input

The input consists of a single line containing n natural numbers separated by spaces, representing the sequence a_1, a_2, ..., a_n.

Output

Output a single integer, the maximum number of negative signs that can be assigned to the elements of the sequence, while ensuring that all partial cumulative sums a_1 + a_2 + ... + a_i are positive.

1Example 1

Input
sequence = [3, 2, 1, 1, 1, 1]
Output
4
Explanation

In the given example, an optimal way to assign the signs could be: +3 +2 -1 -1 -1 -1. This assignment keeps all prefix sums positive, while still maximizing the number of negative signs.

Constraints

Limits and guarantees your solution can rely on.

  • 1 <= n <= 100000
  • 1 <= a_i <= 10^9
public int maximizeNegativeSigns(int[] sequence) {
  // write your code here
}
Input

sequence

[3, 2, 1, 1, 1, 1]

Output

4

Sign in to submit your solution.