【贪心算法题记录】1005. K 次取反后最大化的数组和

本文主要是介绍【贪心算法题记录】1005. K 次取反后最大化的数组和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

题目描述

给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：

选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

以这种方式修改数组后，返回数组 可能的最大和 。

题目分析

我在做这道题时的思路已经和代码写在一起了，我的贪心思路：

局部最优：每次取反，数组和最大；
全局最优：k次取反，数组和最大。

class Solution {
public:int largestSumAfterKNegations(vector<int>& nums, int k) {// 贪心也就是从局部最优推出全局最优，那么局部最优是什么？// 进行k次取反，每次进行取反都满足最大和。 // 每次取反时，我们如何能够满足最大和？// 假设数组中有负数，那么就让最小的负数进行取反// 假设数组中全是正数，那么就让最小的正数进行取反// 总和上述分析，可以发现无论是什么情况，每次都让最小的数进行取反就能获得最大和while(k--) {sort(nums.begin(), nums.end());nums[0] *= -1;}return accumulate(nums.begin(), nums.end(), 0);}
};

代码很简单，虽然ac了，但是如果k值很大，这样处理的效率会非常低。

代码随想录的贪心思路（两次）：

局部最优：让绝对值大的负数变为正数，数组和最大；
全局最优：整个数组和最大。

如果没有负数了：

局部最优：找数值最小的正整数进行反转，当前数值和可以达到最大
全局最优：整个数组和达到最大。

那么整体处理流程就是：

将数组按照绝对值大小从大到小排序
从前向后遍历，遇到负数将其变为正数，同时k--
如果k还大于0，那么反复转变数值最小的元素，将K用完
求和

对应的cpp代码：

class Solution {
static bool cmp(int a, int b) {return abs(a) > abs(b);
}
public:int largestSumAfterKNegations(vector<int>& A, int K) {sort(A.begin(), A.end(), cmp);       // 第一步for (int i = 0; i < A.size(); i++) { // 第二步if (A[i] < 0 && K > 0) {A[i] *= -1;K--;}}if (K % 2 == 1) A[A.size() - 1] *= -1; // 第三步int result = 0;for (int a : A) result += a;        // 第四步return result;}
};