Problem Brief

Maximize the Array Sum After Negating at Most K Elements 🥝

See Amazon online assessment and hiring insights

Given an array A with only positive numbers. We are allowed to negate any entries in the array, (i.e set A[i] = -A[i]). What is the maximum number of entries you can negate in the array such that every prefix sum after the negate operations is positive.

1Example 1

Input

A = [4, 1, 1, 1]

Output

Explanation

We can apply only at-most 3 negate operations, to make A = [4, -1, -1, -1], after the negate operation, The prefix sums of A, p(A) = [4, 3, 2, 1] which are all positive. So that the answer for A is 3.

Draft autosaves locally

public int maxNegations(int[] A) {
  // write your code here
}

Input

[4, 1, 1, 1]

Output