难度: Easy
给你一个整数数组 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 <= 104-100 <= nums[i] <= 1001 <= k <= 104运行时间: 22 ms
内存: 16.2 MB
class Solution:
def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
heap = []
for num in nums:
heapq.heappush(heap, num)
while k > 0:
min_num = heapq.heappop(heap)
heapq.heappush(heap, -min_num)
k -= 1
return sum(heap)
此题解采用最小堆的策略来达到最大化数组和。首先，将数组中的所有元素插入到一个最小堆中，这样可以快速地获取到数组中的最小值。随后，进行k次操作，每次操作都是取出当前堆中的最小元素（这个元素是对当前数组和影响最负面的），然后将其值取反后放回堆中。这样做的目的是尽可能地减少数组中负值的影响或增加正值的影响。经过k次这样的操作后，堆中的所有元素即为修改后的数组，最后计算这些元素的和即为所求的最大数组和。
时间复杂度: O((n+k) log n)
空间复杂度: O(n)
class Solution:
def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
heap = [] # 创建一个最小堆
# 将数组中的所有元素添加到堆中
for num in nums:
heapq.heappush(heap, num)
# 进行k次操作，每次操作都是取反堆中的最小元素
while k > 0:
min_num = heapq.heappop(heap) # 弹出最小元素
heapq.heappush(heap, -min_num) # 将最小元素取反后重新加入堆中
k -= 1
# 返回堆中所有元素的和，即为修改后的数组的最大和
return sum(heap)
使用最小堆的主要原因是最小堆能够快速地提供数组中的最小值。在这个问题中，优先取反影响最负面的数（即最小的数），是最优策略。如果使用数组本身，每次寻找最小值需要O(n)的时间复杂度，而在最小堆中这一操作的时间复杂度仅为O(log n)。使用最大堆则主要用于快速获取最大值，不适合本问题的需求，因为我们需要的是最小值。
是的，如果在k次操作过程中，最小元素变为正数，继续进行取反操作实际上会降低数组的总和。这是因为取反正数会生成负数，从而减少总和。因此，在实际操作时，应当考虑操作的次数和元素的正负，以避免不必要的总和减少。
是的，算法的行为和效果会有所不同。对于全负数数组，取反最小值（即最负的数）可以有效增加数组的总和。如果k次操作后仍有负数，继续取反可以进一步增加总和。对于全正数数组，取反会直接减少数组总和。如果操作次数k是偶数，可以通过成对取反恢复原数值，维持总和不变。如果k是奇数，则会有一个元素保持负值，导致总和减少。
堆结构确实会在操作过程中改变元素的位置，但这不会影响最终计算堆中所有元素的和。堆是一个完全二叉树，其中元素的位置变动确保了堆的性质，但不影响元素本身的值。因此，无论元素在堆中的位置如何变化，堆中所有元素值的总和保持不变。