题目解析力扣1005 题 “K 次取反后最大化的数组和” 要求给定一个整数数组nums和一个整数k你可以执行最多k次取反操作每次操作可以选择数组中的一个元素并将其值取反。请返回经过最多k次取反操作后能得到的最大数组和。核心思路采用贪心算法。为了使数组和最大化应优先将绝对值较大的负数翻转为正数。如果所有负数都翻转后仍有剩余操作次数则应反复翻转绝对值最小的元素即当前数组中的最小正数或零以使总和的损失最小 。算法步骤排序将数组按绝对值从大到小排序。这样能确保优先处理绝对值最大的负数 。第一次贪心翻转负数遍历排序后的数组。如果当前元素是负数且k 0则将其取反nums[i] -nums[i]同时k--。第二次贪心处理剩余翻转次数经过步骤2后如果k仍为奇数即k % 2 1则将数组中绝对值最小的元素即排序后的最后一个元素取反一次。因为偶数次翻转同一个元素相当于没有操作奇数次翻转则相当于取反一次所以只需考虑k的奇偶性 。求和计算并返回最终数组的和。复杂度分析时间复杂度O(n log n)主要由排序操作决定 。空间复杂度O(1) 或 O(log n)取决于排序算法的空间开销。C 代码实现#include vector #include algorithm #include numeric class Solution { public: int largestSumAfterKNegations(std::vectorint nums, int k) { // 1. 按绝对值从大到小排序 std::sort(nums.begin(), nums.end(), [](int a, int b) { return std::abs(a) std::abs(b); }); // 2. 第一次贪心翻转绝对值最大的负数 for (int i 0; i nums.size(); i) { if (nums[i] 0 k 0) { nums[i] -nums[i]; k--; } } // 3. 第二次贪心如果剩余k为奇数翻转绝对值最小的元素即最后一个元素 if (k % 2 1) { nums[nums.size() - 1] -nums[nums.size()1]; } // 4. 计算并返回数组和 return std::accumulate(nums.begin(), nums.end(), 0); } };代码关键点解析自定义排序使用std::sort并传入 lambda 表达式实现按绝对值降序排序这是贪心策略的基础 。两次贪心第一次遍历优先处理负数是局部最优使当前和增加最多第二次处理剩余k值也是局部最优使总和损失最小。两者结合达到全局最优 。剩余k的处理只需判断k的奇偶性因为对同一个元素翻转两次等于没有操作 。参考来源LeetCode刷题复盘笔记—一文搞懂贪心算法之1005. K 次取反后最大化的数组和问题贪心算法系列第六篇数组超过预设的最大数组大小_贪心算法K次取反后最大化的数组和代码随想录算法训练营DAY34|C贪心算法Part.3|1005.K次取反后最大化的数组和、134.加油站、135.分发糖果leetcode-1005 K 次取反后最大化的数组和代码随想录算法训练营Day28 | Leetcode 122 买卖股票的最佳时机 Leetcode 55 跳跃游戏 Leetcode 45 跳跃游戏Ⅱ Leetcode 1005 K次取反求最大值