|
| 1 | +> 很多录友都反馈昨天的题目：[贪心算法：跳跃游戏II](https://mp.weixin.qq.com/s/kJBcsJ46DKCSjT19pxrNYg) 很难，这样我就放心了，哈哈，因为我刚刚讲解贪心的时候一些录友会建议我：贪心没有必要单独讲，直接讲动规就可以了。应该不少没有深入接触过贪心的同学，都会感觉就贪心嘛，有啥难的。现在我们可以发现贪心的道理虽然简单，但解决问题都很巧妙，难度上不照动规差多少。 |
| 2 | +> 今天是一道简单题，关键在于培养贪心的解题思路！ |
1 | 3 |
|
2 | | -``` |
| 4 | + |
| 5 | +# 1005.K次取反后最大化的数组和 |
| 6 | + |
| 7 | +题目地址：https://leetcode-cn.com/problems/maximize-sum-of-array-after-k-negations/ |
| 8 | + |
| 9 | +给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个索引 i 并将 A[i] 替换为 -A[i]，然后总共重复这个过程 K 次。（我们可以多次选择同一个索引 i。） |
| 10 | + |
| 11 | +以这种方式修改数组后，返回数组可能的最大和。 |
| 12 | + |
| 13 | +示例 1： |
| 14 | +输入：A = [4,2,3], K = 1 |
| 15 | +输出：5 |
| 16 | +解释：选择索引 (1,) ，然后 A 变为 [4,-2,3]。 |
| 17 | + |
| 18 | +示例 2： |
| 19 | +输入：A = [3,-1,0,2], K = 3 |
| 20 | +输出：6 |
| 21 | +解释：选择索引 (1, 2, 2) ，然后 A 变为 [3,1,0,2]。 |
| 22 | + |
| 23 | +示例 3： |
| 24 | +输入：A = [2,-3,-1,5,-4], K = 2 |
| 25 | +输出：13 |
| 26 | +解释：选择索引 (1, 4) ，然后 A 变为 [2,3,-1,5,4]。 |
| 27 | + |
| 28 | +提示： |
| 29 | + |
| 30 | +* 1 <= A.length <= 10000 |
| 31 | +* 1 <= K <= 10000 |
| 32 | +* -100 <= A[i] <= 100 |
| 33 | + |
| 34 | +# 思路 |
| 35 | + |
| 36 | +本题思路其实比较好想了，如何可以让数组和最大呢？ |
| 37 | + |
| 38 | +贪心的思路，局部最优：让绝对值大的负数变为正数，当前数值达到最大，整体最优：整个数组和达到最大。 |
| 39 | + |
| 40 | +局部最优可以推出全局最优。 |
| 41 | + |
| 42 | +那么如果将负数都转变为正数了，K依然大于0，此时的问题是一个有序正整数序列，如何转变K次正负，让 数组和 达到最大。 |
| 43 | + |
| 44 | +那么又是一个贪心：局部最优：只找数值最小的正整数进行反转，当前数值可以达到最大（例如正整数数组{5, 3, 1}，反转1 得到-1 比 反转5得到的-5 大多了），全局最优：整个 数组和 达到最大。 |
| 45 | + |
| 46 | +虽然这道题目大家做的时候，可能都不会去想什么贪心算法，一鼓作气，就AC了。 |
| 47 | + |
| 48 | +**我这里其实是为了给大家展现出来 经常被大家忽略的贪心思路，这么一道简单题，就用了两次贪心！** |
| 49 | + |
| 50 | +那么本题的解题步骤为： |
| 51 | + |
| 52 | +* 第一步：将数组按照绝对值大小从大到小排序，**注意要按照绝对值的大小** |
| 53 | +* 第二步：从前向后遍历，遇到负数将其变为正数，同时K-- |
| 54 | +* 第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完 |
| 55 | +* 第四步：求和 |
| 56 | + |
| 57 | +对应C++代码如下： |
| 58 | + |
| 59 | +```C++ |
3 | 60 | class Solution { |
4 | 61 | static bool cmp(int a, int b) { |
5 | | - return abs(a) < abs(b); |
| 62 | + return abs(a) > abs(b); |
6 | 63 | } |
7 | 64 | public: |
8 | 65 | int largestSumAfterKNegations(vector<int>& A, int K) { |
9 | | - sort(A.begin(), A.end(), cmp); |
10 | | - for (int i = A.size() - 1; i >= 0; i--) { |
| 66 | + sort(A.begin(), A.end(), cmp); // 第一步 |
| 67 | + for (int i = 0; i < A.size(); i++) { // 第二步 |
11 | 68 | if (A[i] < 0 && K > 0) { |
12 | 69 | A[i] *= -1; |
13 | 70 | K--; |
14 | 71 | } |
15 | 72 | } |
16 | | - while (K--) A[0] *= -1; |
| 73 | + while (K--) A[A.size() - 1] *= -1; // 第三步 |
17 | 74 | int result = 0; |
18 | | - for (int a : A) result += a; |
| 75 | + for (int a : A) result += a; // 第四步 |
19 | 76 | return result; |
20 | 77 | } |
21 | 78 | }; |
22 | 79 | ``` |
| 80 | +
|
| 81 | +# 总结 |
| 82 | +
|
| 83 | +贪心的题目如果简单起来，会让人简单到开始怀疑：本来不就应该这么做么？这也算是算法？我认为这不是贪心？ |
| 84 | +
|
| 85 | +本题其实很简单，不会贪心算法的同学都可以做出来，但是我还是全程用贪心的思路来讲解。 |
| 86 | +
|
| 87 | +因为贪心的思考方式一定要有！ |
| 88 | +
|
| 89 | +**如果没有贪心的思考方式（局部最优，全局最优），很容易陷入贪心简单题凭感觉做，贪心难题直接不会做，其实这样就锻炼不了贪心的思考方式了**。 |
| 90 | +
|
| 91 | +所以明知道是贪心简单题，也要靠贪心的思考方式来解题，这样对培养解题感觉很有帮助。 |
| 92 | +
|
| 93 | +此时，有没有感觉Carl为了给大家写出优质的题解真的是煞费苦心啊！！ 哈哈，还不赶紧帮忙宣传一波「代码随想录」，让更多的小伙伴知道这里，这样Carl也更有动力写下去！[加油] |
| 94 | +
|
| 95 | +> **我是[程序员Carl](https://github.com/youngyangyang04)，可以找我[组队刷题](https://img-blog.csdnimg.cn/20201115103410182.png)，也可以在[B站上找到我](https://space.bilibili.com/525438321)，本文[leetcode刷题攻略](https://github.com/youngyangyang04/leetcode-master)已收录，更多[精彩算法文章](https://mp.weixin.qq.com/mp/appmsgalbum?__biz=MzUxNjY5NTYxNA==&action=getalbum&album_id=1485825793120387074&scene=173#wechat_redirect)尽在公众号：[代码随想录](https://img-blog.csdnimg.cn/20201124161234338.png)，关注后就会发现和「代码随想录」相见恨晚！** |
| 96 | +
|
| 97 | +**如果感觉题解对你有帮助，不要吝啬给一个👍吧！** |
| 98 | +
|
0 commit comments