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] <= 1001 <= 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 cnt to count the occurrences of each element in the array nums. Then, starting from -100, we iterate through x. If x exists in the hash table, we take m = min(cnt[x], k) as the number of times to negate the element x. We then subtract m from cnt[x], add m to 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 cnt[0] = 0, we need to take the smallest positive number x in cnt, subtract 1 from cnt[x], and add 1 to cnt[-x].
Finally, we traverse the hash table cnt and sum the products of x and 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 nums and the size of the data range of nums, respectively.
PythonJavaC++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())(code-box)
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;
}
}(code-box)
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;
}
};(code-box)
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
}(code-box)
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);
}(code-box)
