Skip to main content
Talentd

Maximize Sum Of Array After K Negations - Solution & Explanation

EasyArrayGreedySorting18 min readAsked at: Amazon, Uber, Google +1
Practice this problem

Problem Statement

Given an integer array nums and an integer k, modify the array in the following way:

  • choose an index i and replace nums[i] with -nums[i].

You should apply this process exactly k times. You may choose the same index i multiple times.

Return the largest possible sum of the array after modifying it in this way.

 

Example 1:

Input: nums = [4,2,3], k = 1
Output: 5
Explanation: Choose index 1 and nums becomes [4,-2,3].

Example 2:

Input: nums = [3,-1,0,2], k = 3
Output: 6
Explanation: Choose indices (1, 2, 2) and nums becomes [3,1,0,2].

Example 3:

Input: nums = [2,-3,-1,5,-4], k = 2
Output: 13
Explanation: Choose indices (1, 4) and nums becomes [2,3,-1,5,4].

 

Constraints:

  • 1 <= nums.length <= 104
  • -100 <= nums[i] <= 100
  • 1 <= k <= 104

Approach Overview

Problem Overview: You are given an integer array and allowed to negate (multiply by -1) exactly k elements. The same index can be chosen multiple times. The goal is to maximize the final sum of the array after performing these operations.

Approach 1: Sorting and Greedy Negation (O(n log n) time, O(1) extra space)

This approach relies on a greedy observation: negating negative numbers increases the total sum. Start by sorting the array so the most negative values appear first. Iterate from left to right and flip each negative number while k > 0. Each negation turns a loss into a gain. If you still have remaining operations after all negatives are handled, the optimal move depends on whether k is odd. When k is odd, negate the element with the smallest absolute value to minimize the damage. Sorting guarantees that the smallest values are processed first, making the greedy decision straightforward. This solution is simple and deterministic, which makes it the most common interview answer when discussing greedy techniques combined with sorting.

Approach 2: Using Priority Queue (Min-Heap) (O(k log n) time, O(n) space)

A min-heap provides a dynamic way to always access the smallest element in the array. Insert all numbers into a min-heap. For each of the k operations, extract the smallest value, negate it, and push it back into the heap. This guarantees that the currently most harmful value is flipped each time. The heap automatically reorders elements after each insertion, so you always operate on the optimal candidate. After performing k negations, sum all elements in the heap to compute the result. This method is useful when you want the algorithm to adapt after every operation rather than relying on a single sorted order. It highlights how priority queues can repeatedly expose the best greedy choice.

Recommended for interviews: The sorting-based greedy solution is typically expected. It shows that you understand the core insight: flipping negative numbers increases the sum, and a leftover odd operation should affect the smallest absolute value. Mentioning the heap approach demonstrates deeper understanding of greedy selection structures, but the sorted greedy implementation is simpler and runs in O(n log n) time with minimal overhead.

Approach 1: Approach 1: Sorting and Greedy Negation

Approach 1: Sorting and Greedy Negation

This approach involves sorting the array first, which helps address the negativity in a prioritized fashion. By sorting, negative numbers are brought to the forefront. The plan is to turn all negative numbers positive for immediate gains. After flipping the necessary negatives or using up the flips, if flips remain, we aim them repeatedly at the smallest number in terms of absolute value to ensure no more productive use of a negation exists.

The C solution uses the standard qsort to sort the array. The core logic emphasizes negating the smallest negative numbers first, iterating through the array until either all negative numbers are converted or k negations are exhausted. Should negations remain post initial conversion, an odd count of k means a further single alteration is advantageous, specifically targeting the smallest number.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as the sorting is done in-place.

Try this approach in the editor →

Approach 2: Approach 2: Using Priority Queue (Min-Heap)

Approach 2: Using Priority Queue (Min-Heap)

A priority queue (or min-heap) will provide an elegant method to always operate on the smallest element. The process involves inserting all numbers into a heap, then multiple negations individualizing the smallest available value until k operations are exhausted. This method efficiently manages both negation and retrieval of minimal elements.

The C++ implementation uses a min-heap, inserting all numbers initially. We invoke k negations, ensuring to log the negated value back into the heap, thus retaining a valid minimum tracking mechanism. The strategy processes/instruments flipping k times and sums up the remainder through a cumulative heap pop.

Code

C++PythonJava

C++

Python

Java

Complexity

Time Complexity: O(n + k log n), where n is for heap initialization and k log n for operations.
Space Complexity: O(n) for the priority queue.

Try this approach in the editor →

Approach 3: Greedy + Counting

We observe that to maximize the sum of the array, we should try to turn the smallest negative numbers into positive numbers.

Given that the range of elements is [-100, 100], we can use a hash table cnt to count the occurrences of each element in the array nums. Then, starting from -100, we iterate through x. If x exists in the hash table, we take m = min(cnt[x], k) as the number of times to negate the element x. We then subtract m from cnt[x], add m to cnt[-x], and subtract m from k. If k becomes 0, the operation is complete, and we exit the loop.

If k is still odd and cnt[0] = 0, we need to take the smallest positive number x in cnt, subtract 1 from cnt[x], and add 1 to cnt[-x].

Finally, we traverse the hash table cnt and sum the products of x and cnt[x] to get the answer.

The time complexity is O(n + M), and the space complexity is O(M). Here, n and M are the length of the array nums and the size of the data range of nums, respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Sorting and Greedy Negation

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as the sorting is done in-place.

Approach 2: Using Priority Queue (Min-Heap)

Time Complexity: O(n + k log n), where n is for heap initialization and k log n for operations.
Space Complexity: O(n) for the priority queue.

Greedy + Counting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting and Greedy NegationO(n log n)O(1)Best general solution. Simple greedy logic after sorting the array.
Priority Queue (Min-Heap)O(k log n)O(n)Useful when repeatedly selecting the smallest element after each operation.

Video Solution

LeetCode 1005: Maximize Sum Of Array After K Negations - Interview Prep Ep 38 • Fisher Coder • 3,001 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximize Sum Of Array After K Negations easy or hard?
The problem is classified as Easy because the key insight is straightforward once you recognize the greedy pattern. Flipping negative numbers increases the sum, and handling the leftover odd operation with the smallest absolute value completes the logic.
Maximize Sum Of Array After K Negations Python/Java solution
Python and Java implementations typically follow the same greedy idea. Sort the array, flip negative elements while K > 0, then adjust the smallest absolute value if K remains odd. Both languages achieve O(n log n) time complexity using built-in sorting utilities.
How to solve Maximize Sum Of Array After K Negations in O(n)?
A near O(n) approach can be achieved with counting or bucket techniques when the value range is small. Track frequencies of numbers, flip negatives first, and adjust the smallest absolute value if an odd operation remains. In general interview settings, the standard solution is O(n log n) using sorting.
What is the best approach for Maximize Sum Of Array After K Negations?
The best approach uses a greedy strategy with sorting. Sort the array, flip negative numbers while K is available, and if operations remain with K being odd, negate the element with the smallest absolute value. This runs in O(n log n) time and O(1) extra space and is the solution most interviewers expect.
Is Maximize Sum Of Array After K Negations asked at Google/Amazon/Meta?
This problem represents a classic greedy optimization pattern and has appeared in interviews at companies like Amazon and other large tech firms. Variations that require repeatedly selecting the smallest element or maximizing array sum after operations are common screening questions.
What data structure is used in Maximize Sum Of Array After K Negations?
Two common structures appear in solutions: sorting the array and using a min-heap (priority queue). Sorting enables a greedy pass over negative values, while the heap approach repeatedly retrieves the smallest element for negation.
What is the time complexity of Maximize Sum Of Array After K Negations?
The common greedy solution runs in O(n log n) time due to sorting the array. After sorting, a single pass handles the negations. A priority queue alternative runs in O(k log n) time because each negation involves removing and reinserting an element into a min-heap.

Ready to solve this problem?

Practice Maximize Sum Of Array After K Negations with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Subsequence of Length K With the Largest Sum