LeetCode 1005. K 次取反后最大化的数组和
题目描述
题意分析
对数组恰好执行
k次操作，每次选择一个位置，将该值改为相反数，求最终数组和的最大值。同一个位置可以反复选择，所以操作次数可能大于数组长度。不能把要求理解成最多操作
k次：即使所有数都已经非负，剩余次数仍要用完。但同一个位置取反两次会恢复原值，因此多余次数只需区分奇偶性，无需逐次模拟。
解法：排序 + 贪心
核心思路
[!blue]
对负数取反会增加数组和，增加量等于其绝对值的两倍；负得越多，收益越大。先升序排序，再从最小的负数开始翻正，直到次数用尽或负数全部处理完，就能优先取得最大的收益。
如果操作次数不足以处理所有负数，选择最小的这些负数最优：把一次操作从较小收益的负数换到更小的负数，结果只会变大。正数取反会降低总和，也不应挤占尚可获得正收益的负数操作。
若还有次数剩余，说明所有负数都已变成非负数。剩余偶数次可以在同一个位置成对取反，完全不改变结果；剩余奇数次则至少要让某个位置最终多取反一次。为了损失最小，应选绝对值最小的元素，只扣除它绝对值的两倍即可。
多取反多个非负元素只会增加损失，因此一次最小损失加上若干对抵消操作就足够。存在零时，最小绝对值为零，额外奇数次也不会降低总和，仍由同一公式处理。
翻正负数后，数组不再保证原来的升序，不能直接认定第一个位置的绝对值最小。重新线性扫描，累计当前和并找到
minAbs；最后按剩余k的奇偶决定是否扣除2 * minAbs。题目只要求最大和，不需要真的执行剩余的抵消操作。
解题步骤
- 将数组升序排序。
- 从最小负数开始依次取反，每次减少一次剩余操作数，直到没有负数或次数用尽。
- 扫描当前数组，计算总和及最小绝对值。
- 剩余次数为偶数时直接返回总和，为奇数时减去最小绝对值的两倍。
代码实现
class Solution {
public int largestSumAfterKNegations(int[] nums, int k) {
Arrays.sort(nums);
// 先翻最小的负数，使每次操作带来的增益最大。
for (int i = 0; i < nums.length && nums[i] < 0 && k > 0; i++) {
nums[i] = -nums[i];
k--;
}
int sum = 0;
int minAbs = Math.abs(nums[0]);
for (int num : nums) {
sum += num;
minAbs = Math.min(minAbs, Math.abs(num));
}
// 剩余偶数次可抵消；奇数次只承担最小绝对值的损失。
return (k & 1) == 0 ? sum : sum - 2 * minAbs;
}
}
import "sort"
func largestSumAfterKNegations(nums []int, k int) int {
sort.Ints(nums)
// 先翻最小的负数，使每次操作带来的增益最大。
for i := 0; i < len(nums) && nums[i] < 0 && k > 0; i++ {
nums[i] = -nums[i]
k--
}
sum := 0
minAbs := nums[0]
if minAbs < 0 {
minAbs = -minAbs
}
for _, v := range nums {
sum += v
abs := v
if abs < 0 {
abs = -abs
}
if abs < minAbs {
minAbs = abs
}
}
// 剩余偶数次可抵消；奇数次只承担最小绝对值的损失。
if k%2 == 1 {
sum -= 2 * minAbs
}
return sum
}
复杂度分析
- 时间复杂度：$O(n\log(n+1))$，排序占主导，其余为线性扫描。
- 空间复杂度：除排序所用的辅助空间外为 $O(1)$；输入数组会被原地修改。
关键点总结
[!green]
- 优先取反最小负数，而不是按原出现顺序选择。
- 最小绝对值可以在取反前或取反后求：取反不改变绝对值。
- 偶数次操作可以抵消，奇数次只保留一次最小损失。
易错点总结
[!yellow]
- 负数处理完就忽略剩余次数：题目要求恰好操作，奇数次残余可能带来不可避免的损失。
- 翻正后直接取数组首项作为最小值：数组的顺序已经被改动，应重新检查最小绝对值。
- 不分正负按原顺序取反：应优先选择收益最大的负数，而不是随意使用次数。
- 把同一位置限制为只能操作一次：题目允许重复选择，偶数次操作可以在一个位置抵消。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1975. 最大方阵和 | 中等 | 同样关注取反的奇偶性与最小绝对值，原题一次翻相邻两项，本题操作数固定且每次只翻一项。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！