https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/
看着简单但是写si人的一题。
java">class Solution {public int largestSumAfterKNegations(int[] nums, int k) {Arrays.sort(nums);//排序int last_negative=-1,first_positive=-1;//最后一个负数位置,第一个正数位置//计数int count_zero=0;int count_negative=0;int count_positive=0;for(int i=0;i<nums.length;i++){if(nums[i]<0){//负数last_negative=i;count_negative++;}else if(nums[i]>0){//正数if(count_positive==0){//前面,没有出现过正数first_positive=i;}count_positive++;}else{//0count_zero++;}}//开始变化if(count_negative>=k){//1.有足够的负数。负数变正数。for(int i=0;i<k;i++){//修改k次nums[i]=-nums[i];}}else if(0<count_negative&&count_negative<k){//2.有负数,但不够。//先修改已有的负数for(int i=0;i<count_negative;i++){//从前到后,修改所有负数。剩下的交给0nums[i]=-nums[i];} int left=k-count_negative;//还需要修改的次数if(left%2==0){// 2.1 还剩下偶数次//不用改了}//2.2 有零。修改0else if(count_zero>0){//也可以说不用改了}else{//2.3 有负数,但不够,还剩奇数次,还没有0int a=Integer.MAX_VALUE;int b=Integer.MAX_VALUE;if(count_positive>0){//有正数a=nums[first_positive];}if(count_negative>0){b=nums[last_negative];}//取绝对值小的数if(Math.abs(a)<Math.abs(b)){nums[first_positive]=-nums[first_positive];}else{nums[last_negative]=-nums[last_negative];}}}else if(count_negative==0){//3.没有负数if(count_zero!=0){//3.1 有零。不用改了。}else{//3.2 没有零。if(k%2==0){//偶数次,变回自己//不用改了}else{//修改最小的正数if(count_positive!=0){nums[first_positive]=-nums[first_positive];}}}}int sum=0;for(int num:nums)sum+=num;return sum;}
}
/**
把负数变成正的,下标越小越好
不想继续改变,如果有0,就改变0
把正数变成负的,下标越小越好
变k次,可以多次选择同一个下标。*/
网上的思路
第一步:将数组按照绝对值大小从大到小排序,注意要按照绝对值的大小
第二步:从前向后遍历,遇到负数将其变为正数,同时K–
第三步:如果K还大于0,那么反复转变数值最小的元素,将K用完
第四步:求和