：负负得正的极致——「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; } };深度辨析：为什么要按绝对值排序？
如果我们只按普通升序排序[-4, -3, -1, 2, 5]：
处理完负数后，数组变成
[4, 3, 1, 2, 5]。如果此时
k剩 1，我们需要找最小的数。在普通排序后的数组里，最小的数
1在中间位置，找起来比较麻烦（需要再次遍历或排序）。
而按绝对值降序排序[5, -4, -3, 2, -1]：
处理完后变成
[5, 4, 3, 2, -1]（假设 -1 没被翻，或者翻了变成 1）。无论如何，绝对值最小的那个数，永远在数组的末尾。
这让第二步处理变得只有 $O(1)$ 的复杂度。
深度复杂度分析
时间复杂度：O(N log N)
主要消耗在排序上。
遍历和求和都是 $O(N)$。
空间复杂度：O(1)
如果是 C++ 的
sort，通常需要 $O(\log N)$ 的栈空间，但不需要额外数组。
总结：贪心的“优先级”
这道题教会了我们如何建立贪心优先级：
最高优先级：消除“大负数”（收益最大）。
次高优先级：消除“小负数”。
最低优先级（迫不得已）：牺牲“小正数”（损失最小）。
通过排序，我们将这些优先级线性化，从而一趟扫描解决问题。
下一题预告：加油站
接下来我们要挑战贪心算法中最经典、也最容易让人懵圈的题目——“加油站”。
你有一个油箱无限大的车，想绕环形公路跑一圈。
每个加油站有油
gas[i]，去下一站消耗cost[i]。你需要找一个起点，保证能跑完一圈。
贪心策略非常神奇：如果你尝试从 A 跑到 B，发现油不够了，那么A 和 B 之间的所有站点都不可能作为起点。为什么？
准备好发车了吗？下期见！