LeetCode-1005-K次取反后最大化的数组和-贪心算法

题目描述：
给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
以这种方式修改数组后，返回数组 可能的最大和 。

LeetCode-1005题目链接

思路见注释~

代码实现

class Solution {/*** 先分情况：* ① 当数组中有正有负：优先将负数取反，负数中优先对找绝对值最大的进行取反；* ② 当数组中全是正数：如果还有机会则找绝对值最小的进行取反**  步骤：*  ① 按绝对值从大到小进行排序*  ② 从前往后遍历数组，遇到负数就取反，当 k 还没用完，判断奇偶，是奇数则对最后一个元素取反，偶数不操作*  ③ 求数组的和再返回即可*/public int largestSumAfterKNegations(int[] nums, int k) {if (nums.length == 1){if (k%2==0){//偶数，等于本身return nums[0];}else {return -nums[0];// 奇数，会变成相反数}}int sum = 0;// 对数组进行排序是重点，这个地方我掌握的并不熟nums = IntStream.of(nums).boxed().sorted((o1,o2) -> Math.abs(o2) - Math.abs(o1)).mapToInt(Integer::intValue).toArray();
//        Arrays.sort((x,y)->Math.abs(y) - Math.abs(x));
//        Arrays.asList(nums).stream().sorted((x,y)->Math.abs(y) - Math.abs(x)).toArray();// 第一次遍历取反for (int i = 0; i < nums.length; i++) {if (nums[i] <0 && k>0){nums[i] *= -1;k--;}}if (k > 0){if (k % 2==1){nums[nums.length-1] *= -1;// 取反}}// 第一种求和方法：第二次遍历求和
//        for (int i = 0; i < nums.length; i++) {
//            sum += nums[i];
//        }return Arrays.stream(nums).sum();//第二种求和方法}
}