题目描述
给定一个整数数组 A,我们只能用以下方法修改该数组:我们选择某个索引 i 并将 A[i] 替换为 -A[i],然后总共重复这个过程 K 次。(我们可以多次选择同一个索引 i。)
以这种方式修改数组后,返回数组可能的最大和。
题目示例
输入:A = [4,2,3], K = 1
输出:5
解释:选择索引 (1,) ,然后 A 变为 [4,-2,3]。
解题思路
使用贪心算法,两次贪心策略解决该题,首先将数组按照绝对值从大到小排序,然后进行以下两次贪心策略。
- 第一次贪心,我们取反,首先取反绝对值最大的负数,也就是最小值。如果第一次贪心正好消耗完 k,就不需要第二次贪心了。
- 第二次贪心,如果我们按照第一次贪心之后,还有取反次数,我们再将数组的最后一个元素(因为第一次贪心完成后,如果还有取反次数,代表数组所有的负数已经全被取反,数组只剩正数,数组最后一个元素即为最小值)进行取反(如果 k 还剩奇数的话,因为偶数的话来回取反还是原来的值,所以就不用取反了)
最后将取反完成的数组取总和返回结果。
参考代码
class Solution {
public int largestSumAfterKNegations(int[] nums, int k) {
// 将数组按照绝对值大小排序
nums = IntStream.of(nums)
.boxed()
.sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))
.mapToInt(Integer::intValue).toArray();
// 第一次贪心,将最大的负数取反
for(int i = 0; i < nums.length; i++) {
if(nums[i] < 0 && k > 0) {
nums[i] *= -1;
k--;
}
}
// 第二次贪心,如果还有取反机会,将最小数字取反
if(k % 2 == 1) {
nums[nums.length - 1] *= -1;
}
// 取修改完数组的总和
return Arrays.stream(nums).sum();
}
}