[数据结构与算法]0贪心算法简单 LeetCode1005. K 次取反后最大化的数组和

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

描述

给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个索引 i 并将 A[i] 替换为 -A[i]，然后总共重复这个过程 K 次。（我们可以多次选择同一个索引 i。）
以这种方式修改数组后，返回数组可能的最大和。

分析

贪心思想，每一次局部的最优解最终会构成全局的最优解。
本题而言，分为两种情况：

1. 负数的个数小于等于K。想要取得最大的和，应该优先反转绝对值大的负数。
2. 负数的个数大于K。想要取得最大的和，先把所有的负数反转成为正数，剩余的次数一直反转绝对值最小的那个数。

不管是1还是2，都要反转负数且优先反转绝对值较大的负数，因此，按照绝对值由大到小遍历数组，反转遍历到的负数，每反转一次，k–。根据前面的分析，此时，有两种情况：
1.k减小为0。算数组总和，返回结果。
2.k不为0。剩余k的次数一直反转绝对值最小的那个数。

为什么注释报错呢？？？？比较器泛型不可以是int类型的数组吗？

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
    	// Arrays.sort(nums,new Comparator<Integer>(){
        //     public int compare(Integer a, Integer b){
        //         return Math.abs((int)b) - Math.abs((int)a);
        //     }
        // });
        int n = nums.length;
        Integer[] num = new Integer[n];
        for(int i = 0; i < n; i++) 
            num[i] = nums[i];//new Integer(A[i]);自动装箱
        //让数组按绝对值由大到小排列
        Arrays.sort(num, (a,b)->{//逆序排序
            return Math.abs(b) - Math.abs(a);
        });
        //按按绝对值由大到小反转负数
        for(int i = 0; i < num.length && k > 0; i++){
            if(num[i] < 0){
                num[i] *= -1;
                k--;
            }
        }
        //若k不为0，剩余k的次数一直反转绝对值最小的那个数
        while(k != 0){
            num[num.length-1] *= -1;
            k--;
        }
        int res = 0;
        for(int a : num){
            res += a;
        }
        return res;
    }
}