Maximize Sum Of Array After K Negations

Difficulty: Easy | Acceptance: 53.80% | Paid: No Topics: Array, Greedy, Sorting

Given an integer array nums and an integer k, modify the array as follows:

Choose an index i and replace nums[i] with -nums[i]. You should perform this operation exactly k times. You may choose the same index multiple times.

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

Examples

Example 1

Input: nums = [4,2,3], k = 1
Output: 5
Explanation: Choose indices (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 (2, 4) and nums becomes [2,-3,1,5,4].

Constraints

1 <= nums.length <= 10⁴
-100 <= nums[i] <= 100
1 <= k <= 10⁴

Sorting Approach

Intuition To maximize the sum, we should prioritize converting negative numbers to positive numbers, as this yields the highest gain ($2 \times |num|$). Sorting allows us to easily access the smallest numbers (most negative) first. If we have remaining operations ($k$) after converting all negatives, we check if $k$ is odd. If it is, we flip the number with the smallest absolute value (which minimizes the loss).

Steps

• Sort the array in ascending order.
• Iterate through the array. If the current number is negative and we still have operations ($k > 0$), flip the number to positive and decrement $k$.
• If $k$ reaches 0, break the loop.
• If $k$ is still greater than 0 after the loop, it means all numbers are non-negative.
• If $k$ is odd, we must flip one number. To minimize the impact, we flip the smallest number in the array (which is now at index 0 if we re-sort, or we can find the minimum absolute value).
• Calculate the sum of the array.

class Solution:
    def largestSumAfterKNegations(self, nums: list[int], k: int) -> int:
        nums.sort()
        for i in range(len(nums)):
            if nums[i] < 0 and k > 0:
                nums[i] = -nums[i]
                k -= 1
            else:
                break
        
        if k % 2 != 0:
            nums.sort()
            nums[0] = -nums[0]
            
        return sum(nums)

Complexity

• Time: O(N log N) due to sorting.
• Space: O(1) or O(N) depending on the sorting implementation.
• Notes: Sorting is efficient and handles the “smallest absolute value” logic cleanly.

Priority Queue Approach

Intuition We can use a Min-Heap (Priority Queue) to always access the smallest number in the array in O(1) time (with O(log N) extraction/insertion). In each of the $k$ operations, we extract the smallest number, negate it (which makes it positive or larger), and push it back into the heap. This greedy strategy ensures that we are always maximizing the sum at every step.

Steps

• Transform the array into a min-heap.
• Loop $k$ times:
  • Pop the smallest element from the heap.
  • Push the negated value of that element back into the heap.
• After $k$ operations, sum up all elements remaining in the heap.

import heapq

class Solution:
    def largestSumAfterKNegations(self, nums: list[int], k: int) -> int:
        heapq.heapify(nums)
        for _ in range(k):
            val = heapq.heappop(nums)
            heapq.heappush(nums, -val)
        return sum(nums)

Complexity

• Time: O(N + K log N) to build the heap and perform K operations.
• Space: O(N) to store the heap.
• Notes: This approach is conceptually simple and handles the logic of “always flip the smallest” naturally without explicit sorting steps for the remaining K.