214.贪心算法：K次取反后最大化的数组和（力扣）

class Solution {
public:int largestSumAfterKNegations(vector<int>& nums, int k) {int sum = 0;// 进行k次取反操作while (k > 0){// 对数组进行排序sort(nums.begin(), nums.end());// 将最小的元素取反nums[0] = -nums[0];// 减少k的值k--;}// 计算数组的总和for (int num : nums){sum += num;}return sum;}
};

核心思想

• 每次都取反数组中绝对值最小的元素，以确保每次取反操作都对数组总和的影响最小化。
• 通过排序，找到当前数组中的最小元素，并对其进行取反操作。
• 重复上述步骤，直到完成 k 次取反操作。

考虑 nums = [3, -1, 0, 2] 和 k = 3：

1. 第一次操作：

   • 排序后：[-1, 0, 2, 3]
   • 取反最小元素：[1, 0, 2, 3]
   • k = 2

2. 第二次操作：

   • 排序后：[0, 1, 2, 3]
   • 取反最小元素：[0, -1, 2, 3]
   • k = 1

3. 第三次操作：

   • 排序后：[-1, 0, 2, 3]
   • 取反最小元素：[1, 0, 2, 3]
   • k = 0

最后计算总和：1 + 0 + 2 + 3 = 6，返回 6。