【无标题】贪心算法（5）（java）k次取反后最大化的数组和

        题目：给定一个整数数组 `nums` 和一个整数 `k`，你可以进行最多 `k` 次取反操作。每次操作可以选择数组中的一个元素并将其取反（即 `x` 变为 `-x`）。最终返回经过 `k` 次取反操作后，数组可能的最大总和。

解法：分情况讨论。

设：整个数组中负数的个数是m个

1.m>k: 把前k小负数转化成正数

2.m==k:把所有负数全部转化成正数

3.m<k: 1..先把所有负数变成正数

            2.k-m的奇偶性1...偶数：直接忽略

                                    2...奇数：挑选当前数组中最小的数，变成负数

import java.util.Arrays;public class Solution {public int largestSumAfterKNegations(int[]nums,int k){int m=0,minElem=Integer.MAX_VALUE,n=nums.length;//统计负数个数，记录绝对值最小的元素for(int x:nums){if(x<0)m++;//负数计数minElem=Math.min(minElem,Math.abs(x));}//分类讨论int ret=0;if(m>k){   //情况一：负数个数多于k次反转Arrays.sort(nums);//排序数组for(int i=0;i<k;i++){//翻转前k个负数ret -= nums[i];//剩余元素直接累加}for(int i=k;i<n;i++){ret += nums[i];}}else{//负数个数小于等于k次翻转//把负数全部变为正数for(int x:nums)ret+=Math.abs(x);if((k-m)%2!=0){//剩余奇数次需调整最小值ret-=minElem*2;//减去两倍·最小值}}return ret;}public static void main(String[] args) {Solution solution=new Solution();int [] nums={2,-3,-1,5,-4};int result= solution.largestSumAfterKNegations(nums,2);System.out.println(result);}
}