贪心算法5javak次取反后最大化的数组和
目录
贪心算法（5）（java）k次取反后最大化的数组和
题目：给定一个整数数组 nums 和一个整数 k，你可以进行最多 k 次取反操作。每次操作可以选择数组中的一个元素并将其取反（即 x 变为 -x）。最终返回经过 k 次取反操作后，数组可能的最大总和。
解法：分情况讨论。
设：整个数组中负数的个数是m个
- 1
- .m>k
- 把前k小负数转化成正数
m==k :把所有负数全部转化成正数
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);
}
}