1005. Maximize Sum of Array After K Negations

The problem

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 <= 10⁴
-100 <= nums[i] <= 100
1 <= k <= 10⁴

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.

Python

def largest_sum_after_k_negations(nums, k):
    nums.sort()
    for i in range(len(nums)):
        if nums[i] < 0 and k > 0:
            nums[i] = -nums[i]
            k -= 1
    sum_nums = sum(nums)
    min_element = min(nums)
    if k % 2 == 1:
        sum_nums -= 2 * min_element
    return sum_nums

nums = [3, -1, 0, 2]
k = 3
result = largest_sum_after_k_negations(nums, k)
print(f"Output: {result}")

Java

import java.util.Arrays;

public class MaximizeSum {
    public static int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length && k > 0; i++) {
            if (nums[i] < 0) {
                nums[i] = -nums[i];
                k--;
            }
        }
        int sum = 0;
        int min = Integer.MAX_VALUE;
        for (int num : nums) {
            sum += num;
            min = Math.min(min, num);
        }
        if (k % 2 == 1) {
            sum -= 2 * min;
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] nums = {3, -1, 0, 2};
        int k = 3;
        int result = largestSumAfterKNegations(nums, k);
        System.out.println("Output: " + result);
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int largestSumAfterKNegations(vector<int>& nums, int k) {
    sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size() && k > 0; i++) {
        if (nums[i] < 0) {
            nums[i] = -nums[i];
            k--;
        }
    }
    int sum = 0;
    int minElement = *min_element(nums.begin(), nums.end());
    for (int num : nums) {
        sum += num;
    }
    if (k % 2 == 1) {
        sum -= 2 * minElement;
    }
    return sum;
}

int main() {
    vector<int> nums = {3,-1,0,2};
    int k = 3;
    cout << "Output: " << largestSumAfterKNegations(nums, k) << endl;
    return 0;
}

JavaScript

function largestSumAfterKNegations(nums, k) {
    nums.sort((a, b) => a - b);
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] < 0 && k > 0) {
            nums[i] = -nums[i];
            k--;
        }
    }
    let sum = nums.reduce((acc, num) => acc + num, 0);
    let minElement = Math.min(...nums);
    if (k % 2 === 1) {
        sum -= 2 * minElement;
    }
    return sum;
}

const nums = [3, -1, 0, 2];
const k = 3;
console.log("Output:", largestSumAfterKNegations(nums, k));

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

int largestSumAfterKNegations(int* nums, int numsSize, int k) {
    qsort(nums, numsSize, sizeof(int), compare);
    for (int i = 0; i < numsSize && k > 0; i++) {
        if (nums[i] < 0) {
            nums[i] = -nums[i];
            k--;
        }
    }
    int sum = 0;
    int min = 100;
    for (int i = 0; i < numsSize; i++) {
        sum += nums[i];
        if (nums[i] < min) {
            min = nums[i];
        }
    }
    if (k % 2 == 1) {
        sum -= 2 * min;
    }
    return sum;
}

int main() {
    int nums[] = {3, -1, 0, 2};
    int k = 3;
    int result = largestSumAfterKNegations(nums, 4, k);
    printf("Output: %d\n", result);
    return 0;
}

using System;
using System.Linq;

public class Program
{
    public static int LargestSumAfterKNegations(int[] nums, int k)
    {
        Array.Sort(nums);
        for (int i = 0; i < nums.Length && k > 0; i++)
        {
            if (nums[i] < 0)
            {
                nums[i] = -nums[i];
                k--;
            }
        }
        int sum = nums.Sum();
        int min = nums.Min();
        if (k % 2 == 1)
        {
            sum -= 2 * min;
        }
        return sum;
    }

    public static void Main()
    {
        int[] nums = { 3, -1, 0, 2 };
        int k = 3;
        Console.WriteLine("Output: " + LargestSumAfterKNegations(nums, k));
    }
}

This Python rendition follows intuitive principles by sorting and flipping through readability. Having flipped requisite negatives, any remaining odd k initiates a final adjustment to the minimal integer to tip the balance.

Complexity

Time Complexity: O(n log n) for the sort operation.
Space Complexity: O(1), modifying the array 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.

Python

import heapq

def largest_sum_after_k_negations(nums, k):
    heapq.heapify(nums)
    while k > 0:
        smallest = heapq.heappop(nums)
        heapq.heappush(nums, -smallest)
        k -= 1
    return sum(nums)

nums = [2, -3, -1, 5, -4]
k = 2
result = largest_sum_after_k_negations(nums, k)
print(f"Output: {result}")

Java

import java.util.PriorityQueue;

public class MaximizeSumWithHeap {
    public static int largestSumAfterKNegations(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : nums) {
            minHeap.offer(num);
        }
        while (k > 0) {
            int smallest = minHeap.poll();
            minHeap.offer(-smallest);
            k--;
        }
        int sum = 0;
        while (!minHeap.isEmpty()) {
            sum += minHeap.poll();
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] nums = {2, -3, -1, 5, -4};
        int k = 2;
        int result = largestSumAfterKNegations(nums, k);
        System.out.println("Output: " + result);
    }
}

C++

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int largestSumAfterKNegations(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> minHeap(nums.begin(), nums.end());
    while (k > 0) {
        int smallest = minHeap.top();
        minHeap.pop();
        smallest = -smallest;
        minHeap.push(smallest);
        k--;
    }
    int sum = 0;
    while (!minHeap.empty()) {
        sum += minHeap.top();
        minHeap.pop();
    }
    return sum;
}

int main() {
    vector<int> nums = {2,-3,-1,5,-4};
    int k = 2;
    cout << "Output: " << largestSumAfterKNegations(nums, k) << endl;
    return 0;
}

In Python, heaps are directly managed by the heapq module, arranging the elements initially and incrementally altering the smallest element available, decrementing k accordingly. Post negations, the summation across the heap provides the result.

Complexity

Time Complexity: O(n + k log n)
Space Complexity: O(n) due to heap storage.

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.

TypeScript

function largestSumAfterKNegations(nums: number[], k: number): number {
    const cnt: Map<number, number> = new Map();
    for (const x of nums) {
        cnt.set(x, (cnt.get(x) || 0) + 1);
    }
    for (let x = -100; x < 0 && k > 0; ++x) {
        if (cnt.get(x)! > 0) {
            const m = Math.min(cnt.get(x) || 0, k);
            cnt.set(x, (cnt.get(x) || 0) - m);
            cnt.set(-x, (cnt.get(-x) || 0) + m);
            k -= m;
        }
    }
    if ((k & 1) === 1 && (cnt.get(0) || 0) === 0) {
        for (let x = 1; x <= 100; ++x) {
            if (cnt.get(x)! > 0) {
                cnt.set(x, (cnt.get(x) || 0) - 1);
                cnt.set(-x, (cnt.get(-x) || 0) + 1);
                break;
            }
        }
    }
    return Array.from(cnt.entries()).reduce((acc, [k, v]) => acc + k * v, 0);
}

func largestSumAfterKNegations(nums []int, k int) (ans int) {
	cnt := map[int]int{}
	for _, x := range nums {
		cnt[x]++
	}
	for x := -100; x < 0 && k > 0; x++ {
		if cnt[x] > 0 {
			m := min(k, cnt[x])
			cnt[x] -= m
			cnt[-x] += m
			k -= m
		}
	}
	if k&1 == 1 && cnt[0] == 0 {
		for x := 1; x <= 100; x++ {
			if cnt[x] > 0 {
				cnt[x]--
				cnt[-x]++
				break
			}
		}
	}
	for x, v := range cnt {
		ans += x * v
	}
	return
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Sorting and Greedy Negation	Time Complexity: O(n log n) for the sort operation. Space Complexity: O(1), modifying the array in place.
Approach 2: Using Priority Queue (Min-Heap)	Time Complexity: O(n + k log n) Space Complexity: O(n) due to heap storage.
Greedy + Counting	–

Complexity analysis

Approach	Time	Space	When to Use
Sorting and Greedy Negation	O(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.

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.

Maximize Sum Of Array After K Negations solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Sorting and Greedy Negation

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

Approach 3: Greedy + Counting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Maximize Sum Of Array After K Negations solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Sorting and Greedy Negation

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

Approach 3: Greedy + Counting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems