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

Solutions

Solution 1: 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 \(\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);
}

Comments