K次取反后最大化的数组和
1005.K次取反后最大化的数组和
题目描述
思路
从小到大操作负数
由于数组和要尽可能大，因此应该总是修改负数，而且应该从值最小的负数开始操作。
当给定的K小于等于数组中负数的个数时，按照上述方法，从小到大依次操作每个负数即可。如果K值较大，则需要操作非负数（包括0）。
由于对0进行操作对数组和不会有任何影响，而操作正数会减小数组和，所以：
- 如果数组中存在0，那么可以对它进行多次操作，直到把剩余的操作次数用完；
- 如果数组中不存在0，并且剩余的操作次数是偶数，则对同一个数操作偶数次等价于不进行操作，因此，可以在不见效数组和的前提下，把剩余次数用完；
- 如果数组中不存在0且剩余的修改次数是奇数，则需要使用单独的一次修改将一个正数变为负数，则为使数组和最大，可以选择最小的正数。
Java实现
class Solution {
public int largestSumAfterKNegations(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<Integer, Integer>();
for (int num : nums) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
int ans = Arrays.stream(nums).sum();
for (int i = -100; i < 0; ++i) {
if (freq.containsKey(i)) {
int ops = Math.min(k, freq.get(i));
ans += (-i) * ops * 2;
freq.put(i, freq.get(i) - ops);
freq.put(-i, freq.getOrDefault(-i, 0) + ops);
k -= ops;
if (k == 0) {
break;
}
}
}
if (k > 0 && k % 2 == 1 && !freq.containsKey(0)) {
for (int i = 1; i <= 100; ++i) {
if (freq.containsKey(i)) {
ans -= i * 2;
break;
}
}
}
return ans;
}
}
Python实现
class Solution:
def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
freq = Counter(nums)
ans = sum(nums)
for i in range(-100, 0):
if freq[i]:
ops = min(k, freq[i])
ans += -i * ops * 2
freq[i] -= ops
freq[-i] += ops
k -= ops
if k == 0:
break
if k > 0 and k % 2 == 1 and not freq[0]:
for i in range(1, 101):
if freq[i]:
ans -= i * 2
break
return ans