Question

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

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;
      }
    }
  }
  let ans = 0;
  for (const [key, value] of cnt.entries()) {
    ans += key * value;
  }
  return ans;
}