K次反演最大化数组和立拓题目链接：https://leetcode-cn.com/problems/maximize-sum-of-array-after-k-negations/给定一个整数数组A，我们只能按以下方式修改数组：我们选择一些索引i并将A[i]替换为-A[i]，然后总共重复此过程K次。（我们可以多次选择同一个索引i。）这样修改数组后，返回数组的最大可能和。示例1：输入：A=[4,2,3],K=1输出：5解释：选择索引(1,)，则A变为[4,-2,3]。示例2：输入：A=[3,-1,0,2],K=3输出：6解释：选择索引(1,2,2)，A变为[3,1,0,2]。示例3：输入：A=[2,-3,-1,5,-4],K=2输出：13解释：选择索引(1,4)，则A变为[2,3,-1,5,4].Tips:1<=A.length<=100001<=K<=10000-100<=A[i]<=100这道题的思路其实比较好想，数组sum怎么算最大的？贪心思想，局部最优：让绝对值大的负数变成正数，当前值达到最大值。整体最优：整个数组的总和达到最大值。局部最优可以导致全局最优。那么如果把所有的负数都变成正数，K还是大于0。这时候的问题就是如何把正负数改K次，使得正整数有序序列的数组和最大化。然后又是一个贪心：局部最优：只找最小值的正整数进行反转，当前值可以达到最大值（比如正整数数组{5,3,1}，反转1得到-1比反5得到-5多半出局），全局最优：整个数组求和到最大值。虽然你做这道题的时候可能不会想什么贪心算法，一下子就拿到AC了。我其实就是要给大家看一下经常被大家忽略的贪心思想。这么简单的一道题，我用了两次贪心！那么这道题的解法步骤是：第一步：数组按绝对值从大到大排序小排序，注意绝对值的大小第二步：从前向后遍历，遇到负数时,化为正数,和K--第三步:如果K仍然大于0,则重复改变最小值的元素,用完K第四步:求和对应的C++代码如下:classSolution{staticboolcmp(inta,intb){returnabs(a)>abs(b);}public:intlargestSumAfterKNegations(vector&A,intK){sort(A.begin(),A.end(),cmp);//第一步for(inti=0;i0){A[i]*=-1;K--;}}if(K%2==1)A[A.size()-1]*=-1;//第三步intresult=0;for(inta:A)result+=a;//第四步步骤返回结果；}}；总结贪婪的话题如果简化，就会简单到让人开始怀疑：这不是应该做的吗？这也算算法？我不认为这是贪心？这道题其实很简单，不懂贪心算法的同学也可以做，不过我还是用贪心的思路来讲解整个过程。因为一定有一种贪婪的思维方式！如果没有贪心的思维方式（局部最优，全局最优），很容易陷入贪心。简单题凭感觉做，贪心题不会直接做。事实上，这不会锻炼贪婪的思维。出路。所以，知道是一道贪心的简单题，就要靠贪心的思维方式来解题，这对培养解题的感觉很有帮助。其他语言版本JavaclassSolution{publicintlargestSumAfterKNegations(int[]nums,intK){//将数组按照绝对值从大到小排序，注意绝对值的大小nums=IntStream.of(nums).boxed().sorted((o1,o2)->Math.abs(o2)-Math.abs(o1)).mapToInt(Integer::intValue).toArray();intlen=nums.length;for(inti=0;i0){nums[i]=-nums[i];K--;}}//如果K仍然大于0，则重复改变最小值的元素，用完Kif(K%2==1)nums[len-1]=-nums[len-1];返回数组。stream(nums).sum();}}classSolution{publicintlargestSumAfterKNegations(int[]A,intK){if(A.length==1)return%2==0?A[0]:-A[0];Arrays.sort(A);intsum=0;intidx=0;for(inti=0;i=Math.abs(A[idx+1]))idx++;继续;}A[idx]=-A[idx];}for(inti=0;iint:A=sorted(A,key=abs,reverse=True)#按照绝对值从大到小排列Aforiinrange(len(A)):ifK>0andA[i]<0:A[i]*=-1K-=1ifK>0:A[-1]*=(-1)**K#取A最后一个数只需要写-1returnsum(A)GofunclargestSumAfterKNegations(nums[]int,Kint)int{sort.Slice(nums,func(i,jint)bool{returnmath.Abs??(float64(nums[i]))>math.Abs??(float64(nums[j]))})fori:=0;i0&&nums[i]<0{nums[i]=-nums[i]K--}}ifK%2==1{nums[len(nums)-1]=-nums[len(nums)-1]}结果：=0fori:=0;i{returnMath.abs(b)-Math.abs(a)})for(leti=0;i0){nums[i]*=-1k--}}if(k>0&&k%2===1){nums[nums.length-1]*=-1}k=0returnnums.reduce((a,b)=>{returna+b})};
