力扣 1005. K 次取反后最大化的数组和-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣 1005. K 次取反后最大化的数组和。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目来源：https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/

力扣 1005. K 次取反后最大化的数组和,开始C++吧,leetcode,算法,c++,贪心算法

C++题解1：最直接的想法就是负的变正的，如果负的元素数量小于k，就挑选绝对值大的负数变正；如果负的元素数量大于k，那么还需要根据剩下的k（待变换数）的奇偶性来判断，偶数就不用管了，奇数就减去2倍的绝对值最小数。

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int res = 0, len = nums.size();
        for(int i = 0; i < len; i++) {
            if(nums[i] < 0 && i < k) nums[i] = -nums[i];
            else if(nums[i] == 0 && i < k) k = 0;
            else if(nums[i] > 0 && i < k){
                if((k - i) % 2 != 0) {
                    if(i == 0) {nums[i] = -nums[i];}
                    else {
                        if(nums[i] < nums[i-1]) {nums[i] = -nums[i];}
                        else {res = res - 2 * nums[i-1];}
                    }
                }
                k = 0;
            } 
            res = res + nums[i];
        }
        // k没有变0，说明还需要进行取反操作
        if(k > len && (k - len) % 2 == 1) {
            res = res - 2 * nums[len - 1];
        }
        return res;
    }
};

C++题解2（来源代码随想录）：采用贪心算法的思路来求解。重写了sort的cmp函数。文章来源地址https://www.toymoban.com/news/detail-571200.html

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

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;
    }
};

到了这里，关于力扣 1005. K 次取反后最大化的数组和的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！