Maximize Sum Of Array After K Negations

Link

Description

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

Solution

Greedy Solution 1

See reference (Chinese).

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end(), [](int a, int b) -> bool {
            return abs(a) > abs(b);
        });

        for (int& num : nums) {
            if (num < 0 && k > 0) {
                num *= -1;
                k--;
            }
        }

        if (k % 2) nums[nums.size() - 1] *= -1;
        return accumulate(nums.begin(), nums.end(), 0);
    }
};

• Time complexity: \(O(n\log n)\);
• Space complexity: \(O(1)\).

Greedy Solution 2

See reference (Chinese).

Since we want the sum of the array to be as large as possible, unless absolutely necessary, we should always modify negative numbers, prioritizing the smallest negative number first. This is because changing a negative number \(-x\) to \(x\) will increase the sum of the array by \(2x\), making such a greedy operation optimal.

When the given \(k\) is less than or equal to the number of negative numbers in the array, we can modify each negative number from smallest to largest as described above. However, if the value of \(k\) is larger, then we must modify non-negative numbers (i.e., positive numbers or \(0\)). Since modifying \(0\) will not affect the sum of the array, and modifying positive numbers will decrease the sum of the array, therefore:

• If there is a \(0\) in the array, we can modify it multiple times until we use up the remaining modifications;
• If there is no \(0\) in the array and the remaining number of modifications is even, since modifying the same number twice is equivalent to not modifying it at all, we can also use up the modifications without decreasing the sum of the array;
• If there is no \(0\) in the array and the remaining number of modifications is odd, then we inevitably need to use a single modification to turn a positive number into a negative one (the remaining number of modifications is even, and it will not decrease the sum of the array). To maximize the sum of the array, we would choose the smallest positive number.

It is important to note that in the process of changing negative numbers to positive ones, there might arise (compared to the smallest positive number in the original array) smaller positive numbers, which should not be overlooked.

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        unordered_map<int, int> freq;
        for (int num : nums) freq[num]++;

        int res = accumulate(nums.begin(), nums.end(), 0);

        for (int i = -100; i < 0; i++) {
            if (freq[i]) {
                int ops = min(k, freq[i]);
                res += (-i) * ops * 2;
                freq[i] -= ops;
                freq[-i] += ops;
                k -= ops;
                if (k == 0) break;
            }
        }

        if (k > 0 && k % 2 && !freq[0]) {
            for (int i = 1; i <= 100; i++) {
                if (freq[i]) {
                    res -= i * 2;
                    break;
                }
            }
        }
        return res;
    }
};

• Time complexity: \(O(n + 201)\);
• Space complexity: \(O(201)\).