解题思路

贪心解决:有操作时尽量操作小的比如负数,如果负数操作完还有剩余操作数,则将剩余操作数都用于操作最小的数如果剩余操作数%2==0或者数组中包含0那就说明剩下的操作数可以使当前数组不变,直接return sum,如果以上两项都不符合,那其实剩余操作数可以看成对最小的数进行一次取反操作

需要注意:取反或取正要加减原来的两倍

代码

class Solution {

    //整体思路:有负数时尽量操作最小的负数,没负数时尽量操作最小的正数或者0
    public int largestSumAfterKNegations(int[] nums, int k) {
        int op = 0,sum = 0;
        Arrays.sort(nums);
        List<Integer> index = new ArrayList<>();
        boolean flag = false;//判断有没有0
        for (int i=0;i<nums.length;i++){
            if (nums[i]<0){
                index.add(i);
            }
            else if (nums[i]==0){
                flag = true;
            }
            sum += nums[i];
        }
        while (op!=k){
            if (!index.isEmpty()){
                for (int i=0;i<index.size() && i<k;i++){
                    nums[index.get(i)] = Math.abs(nums[index.get(i)]);
                    sum += nums[index.get(i)]*2;
                    op++;
                }
                index.clear();
                if (op == k){
                    return sum;
                }
            }
            Arrays.sort(nums);
            //剩余操作次数
            int numOpe = k-op;
            if (numOpe%2!=0 && !flag){
                //对最小的数字操作1次
                sum -= nums[0]*2;
            }
            break;
        }
        return sum;
    }
}