题目描述

题干：
给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：

选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

以这种方式修改数组后，返回数组 可能的最大和 。

示例 1：
输入：nums = [4,2,3], k = 1
输出：5
解释：选择下标 1 ，nums 变为 [4,-2,3] 。

示例 2：
输入：nums = [3,-1,0,2], k = 3
输出：6
解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。

示例 3：
输入：nums = [2,-3,-1,5,-4], k = 2
输出：13
解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。

---

题解思路

返回替换之后数组和最大的结果，每个元素可以替换多次，我们要保证和最大要尽可能把最小的负数替换

于是我们可以将数组排序然后从小开始替换，但是这里需要注意的是，每个元素可以替换多次

于是如果我们可以将所有负数全部替换之后k还有剩余，我们就要开始尽可能的少反转非负数

所以我们只需要让现在最小的自然数反复替换就可以保证最后的和为最大结果

---

正确代码

public int largestSumAfterKNegations(int[] nums, int k) {
    Arrays.sort(nums);
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] < 0 && k > 0) {
            nums[i] = -nums[i];
            k--;
        } else break;
    }
    Arrays.sort(nums);
    return Arrays.stream(nums).sum() - (k % 2 == 0 ? 0 : 2 * nums[0]);
}

---

总结

这里反复强调了每个元素可以多次替换，因为第一次我自己确实就按照排序的顺序一路替换下去

当然这里我又进行了一次多余的排序，你可以在第一次遍历的时候记录最小自然数的下标

如果文章存在问题或者有更好的题解，欢迎在评论区斧正和评论，各自努力，最高处见