1005. K 次取反后最大化的数组和（Maximize Sum Of Array After K Negations）

频次 ★★★ · 难度 🟢 · 高频：字节

题目

给定一个整数数组 nums 和一个整数 k，每次操作选择数组中的一个元素取反。共进行 k 次操作（可以多次选择同一个元素），返回可能的最大数组和。

示例：

输入: nums = [4,2,3], k = 1
输出: 5 （选择 -1 取反：-1+2+3+4=5）

输入: nums = [3,-1,0,2], k = 3
输出: 6 （取反 -1 一次，取反 0 两次）

输入: nums = [2,-3,-1,5,-4], k = 2
输出: 13 （取反 -4 和 -3：2+3+1+5+4=13）

思路

贪心（按绝对值排序）：分三步：

1. 按绝对值从大到小排序
2. 从前向后遍历，遇到负数就取反，k— （绝对值大的负数优先翻）
3. 如果 k 还有剩余且为奇数，将绝对值最小的元素取反一次（因为同一个元素反复取反偶数次等于不变，奇数次等于取反一次）

代码

public int largestSumAfterKNegations(int[] nums, int k) {
    // 按绝对值从大到小排序
    Integer[] arr = new Integer[nums.length];
    for (int i = 0; i < nums.length; i++) arr[i] = nums[i];
    Arrays.sort(arr, (a, b) -> Math.abs(b) - Math.abs(a));
 
    for (int i = 0; i < arr.length && k > 0; i++) {
        if (arr[i] < 0) {        // 优先翻转负数
            arr[i] = -arr[i];
            k--;
        }
    }
 
    // k 还有剩余且为奇数，翻转绝对值最小的
    if (k % 2 == 1) {
        arr[arr.length - 1] = -arr[arr.length - 1];
    }
 
    int sum = 0;
    for (int num : arr) sum += num;
    return sum;
}

复杂度

• 时间：O(n log n) —— 排序
• 空间：O(n) —— Integer 数组（排绝对值用）

边界条件

• k = 0：不操作，直接求和
• 全是正数且 k 为偶数：返回值不变（偶数次取反互相抵消）
• 全是正数且 k 为奇数：翻转最小的正数
• 有 0：如果 k 次操作后有剩余，可以反复翻转 0 消耗次数（0 翻转还是 0），不影响结果
• 负数数量 > k：只翻转绝对值最大的 k 个负数

变式

• 455. 分发饼干：同为简单贪心，排序 + 遍历
• 1007. 行相等的最少多米诺旋转：同样是翻转/旋转类贪心

易错点

• 排序按绝对值而非原值：如果按原值排序，负数翻正后可能不在正确位置，难以继续处理
• k 剩余奇数次只需翻转绝对值最小的：反复翻转同一个元素偶数次等于不变，所以只需关注 k 的奇偶性
• 翻转后数组顺序不变：按绝对值排序后，翻转完负数，绝对值最小的元素就在数组末尾（arr[arr.length - 1]）

面试追问

• 为什么按绝对值排序？ 贪心策略：优先翻转绝对值大的负数（收益最大）。如果 k 有剩余，翻转绝对值最小的元素（损失最小）。按绝对值排序后，负数在前（绝对值大的），绝对值最小的在末尾，操作方便
• k 剩余为偶数时为什么不用管？ 同一个元素翻转 2 次等于不变，偶数次翻转可以全部作用在同一个元素上，结果不变

关联题

• 同套路：455. 分发饼干 —— 排序 + 贪心
• 进阶：45. 跳跃游戏 II —— 更复杂的贪心
• 知识点：贪心之”排序+最优处理”模板见贪心