1.5 log 1005.K次取反后最大化的数组和

发布时间:2024年01月05日
class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        int sum=0;
        for(int i=0;i<nums.size();i++){
            sum+=nums[i];
        }
        while(k--){
            int min=0;
            for(int i=0;i<nums.size();i++){
                if(nums[min]>nums[i]) min=i;
            }
            nums[min]=-nums[min];
            sum+=nums[min]*2;
        }
        return sum;
    }
};

取反k次,贪心贪的是每次都取反最小的那个数,因为最小负数取反后收益最大,最小正数取反后损失最小,具体实现就是先求出总和,然后再while循环里面对最小值重新令为其绝对值,循环次数为k,sum再加上两倍最小值的绝对值,循环结束返回sum

?

class Solution {
public:
    static bool cmp(int a,int b){
        return abs(a)>abs(b);
    }
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end(),cmp);
        for(int i=0;i<nums.size();i++){
            if(nums[i]<0&&k>0){
                nums[i]*=-1;
                k--;
            }
        }
        if(k%2){
            nums[nums.size()-1]*=-1;
        }
        int sum=0;
        for(int a:nums){
            sum+=a;
        }
        return sum;
    }
};

?下面这种解法时间复杂度更低,首先对数组的绝对值从大到小排序,然后遍历数组,如果nums[i]为负同时k不为0,则从左到右依次对负数取绝对值,如果k为0了则累加数组就行,如果nums[i]为正了,则先判断k的奇偶,如果为偶数直接累加,如果为奇数则对数组末数值去绝对值,然后累加

文章来源:https://blog.csdn.net/weixin_58515995/article/details/135416177
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。