题目描述

给你一个整数数组 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] 。

提示：

• 1 <= nums.length <= 10^4
• -100 <= nums[i] <= 100
• 1 <= k <= 104

链接：https://leetcode-cn.com/problems/maximize-sum-of-array-after-k-negations

题目大意

对于一个由整数构成的数组 A，每次翻转可以把其中的任意一位翻转成其相反数。要求一定要做 K 次翻转，但是可以翻转相同位置的数字，求翻转之后的数组的最大和。

解题方法

这个题目怎么想呢？

• 我们优先翻转负数翻转成正数，这样和就会变大。那么优先翻转哪个负数呢？肯定是最小的负数，这样求相反数之后会变得最大。
• 那么，当负数翻转完了之后怎么办？那么只能翻转非负数了，所以如果有 0 就一直翻转 0，否则就每次挑正数翻转成负数，翻转之后继续选负数翻转。

总之，这是个贪心算法：每次都翻转数组中最小的数字，翻转 K 次之后，得到的数组拥有最大和。

小根堆

为了快速得到数组中的最小数字，用 min()函数是不行的，因为其时间复杂度是 O(N)。

最好的办法是：维护一个小根堆，每次翻转前取出堆里面的最小数字，翻转之后的结果仍然放入堆中，以便进行下次翻转。

---

下面的动画，是根据题目示例「输入： nums = [2,-3,-1,5,-4], k = 2 输出： 13」所做。

Python代码如下：

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        heapq.heapify(nums)
        for _ in range(k):
            curmin = heapq.heappop(nums)
            heapq.heappush(nums, -curmin)
        return sum(nums)