【贪心算法题记录】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值很大，这样处理的效率会非常低。

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

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

如果没有负数了：

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

那么整体处理流程就是：

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

对应的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;
    }
};