2021.12.28 - SX09-09.K 次取反后最大化的数组和

2021.12.28 - SX09-09.K 次取反后最大化的数组和

文章目录

• 1. 题目
• 2. 思路
• • (1) 贪心算法
• 3. 代码

1. 题目

2. 思路 (1) 贪心算法

• 贪心算法的策略是优先对最小的数进行取反，因此，首先对数组进行快速排序。
• 对于负数，应该尽可能的取反；对于正数，应该尽可能的不取反；特殊地，对于零点两侧的数，应该对绝对值更小的数进行取反。
• 注意！可能遍历数组后k的值仍不为0，若此时k是奇数，则对最后一个元素进行取反。

3. 代码

import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
    }
}

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int res = 0;
        int pre = Integer.MAX_VALUE;
        for (int num : nums) {
            if (k > 0) {
                if (num < 0) {
                    res -= num;
                    pre = -num;
                    k--;
                } else {
                    if ((k & 1) == 0) {
                        res += num;
                    } else {
                        if (num > pre) {
                            res += num - 2 * pre;
                        } else {
                            res -= num;
                        }
                    }
                    k = 0;
                }
            } else {
                res += num;
            }
        }
        if ((k & 1) == 1) {
            res -= 2 * pre;
        }
        return res;
    }
}