FastPrepMaximize the Array Sum After Negating at Most K Elements
Problems/Maximize the Array Sum After Negating at Most K Elements

Maximize the Array Sum After Negating at Most K Elements

Amazon logoAmazon● MediumOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

You are given an array A of n positive integers. You may negate any of its entries. Negating A[i] means changing it to -A[i].

After your changes, every prefix sum must be positive (greater than 0). A prefix sum is the sum of the first k entries, for each k from 1 to n.

For example, with A = [3, 2, 2], you can negate one 2. The array [3, -2, 2] has prefix sums 3, 1 and 3. Negating both 2s gives prefix sums 3, 1 and -1, which fails. So the answer is 1.

Return the largest number of entries you can negate.

Function

maxNegations(A: int[]) → int

Complete the function maxNegations in the editor.

maxNegations has the following parameter:

  • int[] A: the positive values

Returns int: the largest number of entries you can negate

Examples

Example 1

A = [4, 1, 1, 1]return = 3

Keep 4 as it is and negate the three 1s. A becomes [4, -1, -1, -1]. The prefix sums are 4, 3, 2 and 1, and all of them are positive. The first entry can never be negated, because its prefix sum would be -4. So at most 3 entries can be negated. The answer is 3.

Constraints

  • 1 <= n <= 10^5, where n is the length of A
  • 1 <= A[i] <= 10^4

More Amazon interview questions

  • LRU Cache for Query ResultsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Maximal SquareONSITE INTERVIEW · Seen Nov 2026
  • Serialize and Deserialize a Binary TreeONSITE INTERVIEW · Seen Nov 2026
  • Course SchedulePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Course Schedule IIPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Diagonal Traversal of a Binary TreeONSITE INTERVIEW · Seen Nov 2026
  • Minimum Time to Spread Through a GridPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Consistent-Hash Packet RouterPHONE SCREEN · Seen Nov 2026
  • Count Connected ComponentsPHONE SCREEN · Seen Nov 2026
  • Maximize K-Element AND with an Increment BudgetOA · Seen Nov 2026

Similar questions at other companies

  • Minimum Cost K-Capable ModelsMicrosoft · OAMicrosoft interview questions
  • Optimal TransferSnowflake · OASnowflake interview questions
  • Gas Station Loop StartNutanix · OANutanix interview questions
  • Redistribute MegaseedsRubrik · OARubrik interview questions
  • Maximum Distinct Items Within a BudgetAdobe · OAAdobe interview questions
  • Minimum AmountBelvedere Trading · OA
  • Focus on Efficiency (2024 NG)Google · OAGoogle interview questions
  • Running Through Walls with Limited EnergyScale AI · OAScale AI interview questions
  • Make the Array PositiveAtlassian · OAAtlassian interview questions
  • Maximize Compatible Car RidersUber Freight · PHONE SCREEN · ONSITE INTERVIEWUber Freight interview questions

Interview reports that mention this question

  • Amazon Full-Time OA Problems, Earlier Reports (Part 5 of 5)

Amazon interview experiences

  • Amazon Experienced SDE Onsite Questions: 1 Experience
  • Amazon SDE Onsite Interview Questions: 9 Experiences
  • Amazon SDE II and L5 FDE Interview Questions: 4 Experiences
  • Amazon Full-Time OA Problems, Recent Reports (Part 4 of 5)
  • Amazon New Grad OA Problems: Every Task We Have (Part 3 of 5)
See Amazon hiring insights
Saved
class Solution {
    public int maxNegations(int[] A) {
      // write your code here
    }

}
Checking account…