FastPrep
Problem · Array

Maximize the Array Sum After Negating at Most K Elements 🥝

Learn this problem
● MediumAmazonOA
See Amazon hiring insights

Problem statement

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.

Function

maxNegations(A: int[]) → int

Examples

Example 1

A = [4, 1, 1, 1]return = 3
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.

More Amazon problems

drafts saved locally
public int maxNegations(int[] A) {
  // write your code here
}
A[4, 1, 1, 1]
expected3
checking account