GreedyAlgorithm-MaximizedarrayafterKnegativesand

很多记录者反馈昨天的题目：GreedyAlgorithm:JumpingGameII很难，所以我松了一口气，哈哈，因为我刚刚解释了greedy记录俱乐部给我的建议：有不用单独谈贪心，只谈运动规律。很多同学应该觉得自己就是贪心，所以没有什么难度。现在我们可以发现，贪婪原理虽然简单，但是解决问题却非常巧妙，难度和规则相差不大。今天是一道简单的题，关键是要培养贪心的解题思路！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了。“我其实就是来给大家展示一下经常被大家忽略的贪婪思维，这么简单的一道题，我用了两次贪心！”那么这道题的解法步骤是：第一步：将数组从Sort中从大到小进行划分，“注意绝对值的大小”第二步：从前向后遍历，遇到时转为正数为负数，K--第三步：如果K仍然大于0，则重复变化对于最小值的元素，用完K第四步：求和对应的C++代码如下：classSolution{staticboolcmp(inta,intb){returnabs(a)>abs(b);}public:intlargestSumAfterKNegations(vector&A,intK){sort(A.begin(),A.end(),cmp);//第一个stepfor(inti=0;i0){A[i]*=-1;K--;}}while(K--)A[A.size()-1]*=-1;//第三步intresult=0;for(inta:A)result+=a;//第四步returnresult;}};总结如果贪心的话题很简单，就会简单到让人开始怀疑：这不是应该做的吗？它是一种算法吗？我不觉得它很贪心？这道题其实很简单，不懂贪心算法的同学也可以做，不过我还是用贪心的思路来讲解整个过程。因为一定有一种贪婪的思维方式！》如果没有贪心的思维方式（局部最优，全局最优），很容易陷入贪心，简单的题凭感觉做，贪心题不会直接做，其实这样不会锻炼贪心。思维方式。”所以，知道是一道贪心的简单题，就要靠贪心的思维方式来解题，这对培养解题的感觉很有帮助。本文转载自微信公众号《代码随想录》，可通过以下二维码关注。转载本文请联系CodeCaprice公众号。