1005. Maximize Sum Of Array After K Negations

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

Solutions

Solution 1: Greedy + Counting

Thinking

Repeatedly negating the current minimum \(k\) times is optimal. Both \(n\) and \(k\) are at most \(10^4\), but finding the minimum each time needs an extra selection structure. Values lie in \([-100,100]\), so we need not sort the original array.

To maximize the sum we should flip the most negative numbers first. If an odd number of flips remain and there is no zero, the smallest positive value must be flipped once more.

A frequency map consumes flips from \(-100\) to \(-1\), optionally flips the smallest positive, and finally sums value times count.

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 \(\textit{cnt}\) to count the occurrences of each element in the array \(\textit{nums}\). Then, starting from \(-100\), we iterate through \(x\). If \(x\) exists in the hash table, we take \(m = \min(\textit{cnt}[x], k)\) as the number of times to negate the element \(x\). We then subtract \(m\) from \(\textit{cnt}[x]\), add \(m\) to \(\textit{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 \(\textit{cnt}[0] = 0\), we need to take the smallest positive number \(x\) in \(\textit{cnt}\), subtract \(1\) from \(\textit{cnt}[x]\), and add \(1\) to \(\textit{cnt}[-x]\).

Finally, we traverse the hash table \(\textit{cnt}\) and sum the products of \(x\) and \(\textit{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 \(\textit{nums}\) and the size of the data range of \(\textit{nums}\), respectively.

Python3JavaC++GoTypeScript

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        cnt = Counter(nums)
        for x in range(-100, 0):
            if cnt[x]:
                m = min(cnt[x], k)
                cnt[x] -= m
                cnt[-x] += m
                k -= m
                if k == 0:
                    break
        if k & 1 and cnt[0] == 0:
            for x in range(1, 101):
                if cnt[x]:
                    cnt[x] -= 1
                    cnt[-x] += 1
                    break
        return sum(x * v for x, v in cnt.items())

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : nums) {
            cnt.merge(x, 1, Integer::sum);
        }
        for (int x = -100; x < 0 && k > 0; ++x) {
            if (cnt.getOrDefault(x, 0) > 0) {
                int m = Math.min(cnt.get(x), k);
                cnt.merge(x, -m, Integer::sum);
                cnt.merge(-x, m, Integer::sum);
                k -= m;
            }
        }
        if ((k & 1) == 1 && cnt.getOrDefault(0, 0) == 0) {
            for (int x = 1; x <= 100; ++x) {
                if (cnt.getOrDefault(x, 0) > 0) {
                    cnt.merge(x, -1, Integer::sum);
                    cnt.merge(-x, 1, Integer::sum);
                    break;
                }
            }
        }
        int ans = 0;
        for (var e : cnt.entrySet()) {
            ans += e.getKey() * e.getValue();
        }
        return ans;
    }
}

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        unordered_map<int, int> cnt;
        for (int& x : nums) {
            ++cnt[x];
        }
        for (int x = -100; x < 0 && k > 0; ++x) {
            if (cnt[x]) {
                int m = min(cnt[x], k);
                cnt[x] -= m;
                cnt[-x] += m;
                k -= m;
            }
        }
        if ((k & 1) && !cnt[0]) {
            for (int x = 1; x <= 100; ++x) {
                if (cnt[x]) {
                    --cnt[x];
                    ++cnt[-x];
                    break;
                }
            }
        }
        int ans = 0;
        for (auto& [x, v] : cnt) {
            ans += x * v;
        }
        return ans;
    }
};

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
}

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);
}

1005. Maximize Sum Of Array After K Negations

Description

Solutions

Solution 1: Greedy + Counting

Comments