Leetcode 1005 K 次取反后最大化的数组和

题意理解：

? ? ? ? 有k次对元素取反的次数，要求k次取反，消耗完，且使最后的数组和最大。

????????

解题思路：

? ? ? ? 采用贪心的思路来解题。则需要定义局部最优解和全局最优解。

? ? ? ? 全局最优解：最终的数组和最大

? ? ? ? 则我们需要保证绝对值大的数尽可能为正，绝对值最小的数为负。

? ? ? ? 所以为实现该目标，我们首先对数组进行排序，以绝对值大小顺序，从大到小排序

? ? ? ? 若到最后一个元素，k还未消耗完，则对最小的元素进行反复反转。

? ? ? ????????? 若剩余k为正数，则最后最小元素为正

? ? ? ? ????????若剩余k为负数，则最后最小元素为负

? ? ? ? 最终能达到最大序列和的目标。

1.贪心解题

通过IntStream的方式进行排序。

public int largestSumAfterKNegations(int[] nums, int k) {
        int sum=0;
        //1.按绝对值排序
        nums = IntStream.of(nums)
                .boxed()
                .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))
                .mapToInt(Integer::intValue).toArray();
        //2翻转
        for(int i=0;i<nums.length;i++){
            if(nums[i]<0&&k>0){
                nums[i]=nums[i]*-1;
                k--;
            }
            //数组遍历完，k没有消耗完
            if(i==nums.length-1&&k!=0){
                if(k%2==1) nums[i]=nums[i]*-1;
            }
            sum+=nums[i];
        }
        return sum;
    }

2.分析

时间复杂度：O(n)

空间复杂度：O(n)

n为输入数组长度

3.补充

排序1：

IntStream.of(nums)//流式处理
? ? ? ? ? ? ? ? .boxed()//装箱
? ? ? ? ? ? ? ? .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))//定义绝对值比大小的排序
? ? ? ? ? ? ? ? .mapToInt(Integer::intValue).toArray();//转int,转数组，拆箱

jdk8-stream深入详解与运行机制（旧）_jdk stream-CSDN博客

排序2：

Arrays.sort(a,new Comparator<>(){

????????public int compare(int a, int b){

????????????????return a-b;

????????}

});

要求为对象类型

https://www.cnblogs.com/zxLai/p/17838988.html

排序3： 自己实现排序算法