当前位置: 首页> 科技> IT业 > 214.贪心算法:K次取反后最大化的数组和(力扣)

214.贪心算法:K次取反后最大化的数组和(力扣)

时间:2025/7/10 13:07:27来源:https://blog.csdn.net/weixin_63779802/article/details/140278581 浏览次数:0次

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

关键字:214.贪心算法:K次取反后最大化的数组和(力扣)

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: