Maximize the Array Sum After Negating at Most K Elements
Updated
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 = 3Keep 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, wherenis the length ofA1 <= 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