【贪心】leetcode1005K次取反后数组后的最大值

Given an integer array nums and an integer k, modify the array in the following way:

choose an index i and replace nums[i] with -nums[i].
You should apply this process exactly k times. You may choose the same index i multiple times.

Return the largest possible sum of the array after modifying it in this way.

• 1 <= nums.length <= 1e4
• -100 <= nums[i] <= 100
• 1 <= k <= 1e4

题意：定义操作：nums[i]改为-nums[i],进行k次操作（同一个数可以进行多次操作），求数组的最大和

思路：

首先对元素进行排序，因为把一个负数变为正数时，总和变大，所有优先考虑操作负数；

当负数越小，操作后收益越大，所以优先考虑操作绝对值大的负数；

当负数的个数大于k时，只需要操作k次负数；

当负数的个数小于k时，把负数全部操作完后只能操作非负数，操作后总和只能变小或者不变。

（1）如果操作后k的值变为偶数，那么可以相当于不操作，总和不变。

（2）如果操作后k的值变为奇数，那么相当于只操作了一次，那么优先操作绝对值最小的数。

注意：

因为长度1e4，范围-100~100所以优先考虑使用桶排序

排序算法——桶排序_翊夜的博客-CSDN博客_t桶排序

 

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
       Map<Integer,Integer>map=new HashMap<>();
       int t=(int)1e8;
       for(int n:nums){
           map.put(n,map.getOrDefault(n,0)+1);
           t=Math.min(t,Math.abs(n));
       }
       for(int i=-100;i<0&&k>0;i++){
           while(map.getOrDefault(i,0)>0&&k>0){
               map.put(i,map.get(i)-1);
               map.put(-i,map.getOrDefault(-i,0)+1);
               k--;
           }
       }
       int res=0;
       for(int i=-100;i<=100;i++){
           res+=i*map.getOrDefault(i,0);
       }
       if(k%2!=0)res-=2*t;
       return res;
       
  
    }
}