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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | 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())
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 | 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 | 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 | 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
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 | 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;
}
|