FastPrep
Problem · Array

Maximize Negative Signs

Learn this problem
● MediumAmazonOA
See Amazon hiring insights

Problem statement

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.

Function

maximizeNegativeSigns(sequence: int[]) → int

Examples

Example 1

sequence = [3, 2, 1, 1, 1, 1]return = 4

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

  • 1 <= n <= 100000
  • 1 <= a_i <= 10^9

More Amazon problems

drafts saved locally
public int maximizeNegativeSigns(int[] sequence) {
  // write your code here
}
sequence[3, 2, 1, 1, 1, 1]
expected4
checking account