贪心算法专题(七)：负负得正的极致——「K 次取反后最大化数组和」-编程实验室

哈喽各位，我是前端小L。

欢迎来到贪心算法专题第七篇！

题目很简单：给你一个整数数组 nums 和一个整数 k。你必须执行 k 次取反操作（可以选择同一个下标）。最后，让数组的总和最大。

直觉告诉我们：

负数是宝藏：把负数变成正数，总和会蹭蹭往上涨。
绝对值越大越好：把-100变成100，比把-1变成1划算多了。
正数是累赘：如果负数都变完了，k还没用完，我们不得不把正数变回负数。这时候要选最小的正数，因为-1总比-100造成的损失小。

力扣 1005. K 次取反后最大化数组和

https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/

题目分析：

输入：nums数组，k次操作。
目标：最大数组和。
规则：必须操作 K 次。

例子：nums = [2, -3, -1, 5, -4],k = 2

第一次：肯定选-4（绝对值最大），变成4。数组：[2, -3, -1, 5, 4]。
第二次：肯定选-3（剩下里绝对值最大的），变成3。数组：[2, 3, -1, 5, 4]。
结果：2+3-1+5+4 = 13。

核心思维：两次贪心

我们可以把这个过程分为两个阶段：

第一阶段贪心（处理负数）：
- 策略：优先把绝对值最大的负数变成正数。
- 这就要求我们按绝对值大小对数组进行排序。
- 例如[-4, -3, -1, 2, 5]（按绝对值降序是5, -4, -3, 2, -1，或者我们直接处理负数逻辑）。
第二阶段贪心（处理多余的 K）：
- 如果负数都变完了，k还是正数（且是奇数）。
- 策略：找一个当前数值最小的元素进行取反。
- 因为这时候数组全是正数（或0），取反一定会减少总和。为了让总和减少得最少，必须选最小的那个数。

算法流程

为了完美配合这两种贪心策略，我们可以使用一个巧妙的排序方法：按绝对值从大到小排序。

排序：将数组按照绝对值从大到小排序。
- 原数组：[2, -3, -1, 5, -4]
- 排序后：[5, -4, -3, 2, -1](绝对值：5, 4, 3, 2, 1)
第一轮遍历：
- 从头往后走。如果遇到负数且k > 0，就把它变正，k--。
- 此时数组变为：[5, 4, 3, 2, -1](-4和-3变了)。
- 此时k可能还有剩余。
第二轮处理：
- 如果k此时是偶数，不需要操作（对同一个数取反两次等于没变）。
- 如果k是奇数，必须再操作一次。
- 因为我们是按绝对值从大到小排序的，所以数组的最后一个元素，一定是绝对值最小的（也就是数值最小的非负数）。
- 直接对nums[n-1]取反。
求和。

代码实现 (C++)

C++

#include <vector> #include <algorithm> // for sort, abs #include <numeric> // for accumulate using namespace std; class Solution { // 自定义比较函数：按绝对值从大到小排序 static bool cmp(int a, int b) { return abs(a) > abs(b); } public: int largestSumAfterKNegations(vector<int>& nums, int k) { // 1. 按绝对值从大到小排序 sort(nums.begin(), nums.end(), cmp); // 2. 第一步贪心：把绝对值大的负数变成正数 for (int i = 0; i < nums.size(); i++) { if (nums[i] < 0 && k > 0) { nums[i] *= -1; k--; } } // 3. 第二步贪心：如果 k 还没用完（且是奇数） // 此时数组里全是正数（或者0），且最后一个元素绝对值最小 if (k % 2 == 1) { nums[nums.size() - 1] *= -1; } // 4. 求和 int sum = 0; for (int num : nums) { sum += num; } return sum; } };