LeetCode刷题【1005】K 次取反后最大化的数组和

输入：nums = [4,2,3], k = 1
输出：5
解释：选择下标 1 ，nums 变为 [4,-2,3] 。

输入：nums = [3,-1,0,2], k = 3
输出：6
解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。

输入：nums = [2,-3,-1,5,-4], k = 2
输出：13
解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。

马马虎虎优先队列

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        int sum = 0;
        PriorityQueue<Integer> queue = new PriorityQueue<>();

        int absMin = 101;
        for (int num : nums) {
            absMin = Math.min(absMin,Math.abs(num));
            if (num >= 0){
                sum += num;
            }else{
                queue.offer(num);
            }
        }
        if (queue.size()>0){
            //把绝对值较大的负数尽量翻转
            while (!queue.isEmpty() && k > 0){
                sum -= queue.poll();
                k--;
            }
            if (k==0){
                //翻转次数用完了，还有数字没翻转
                while (!queue.isEmpty()){
                    sum += queue.poll();
                }
                return sum;
            }
        }
        if (k%2 == 0){
            return sum;
        }else{
            return sum - 2*absMin;
        }
    }
}