貪心算法：K次取反后最大化的數(shù)組和
很多錄友都反饋昨天的題目：貪心算法：跳躍游戲II 很難，這樣我就放心了，哈哈，因為我剛剛講解貪心的時候一些錄友會建議我：貪心沒有必要單獨講，直接講動規(guī)就可以了。應(yīng)該不少同學(xué)都會感覺就貪心嘛，有啥難的。現(xiàn)在我們可以發(fā)現(xiàn)貪心的道理雖然簡單，但解決問題都很巧妙，難度上不照動規(guī)差多少。
今天是一道簡單題，關(guān)鍵在于培養(yǎng)貪心的解題思路!
K次取反后最大化的數(shù)組和題目地址：https://leetcode-cn.com/problems/maximize-sum-of-array-after-k-negations/
給定一個整數(shù)數(shù)組 A，我們只能用以下方法修改該數(shù)組：我們選擇某個索引 i 并將 A[i] 替換為 -A[i]，然后總共重復(fù)這個過程 K 次。(我們可以多次選擇同一個索引 i。)
以這種方式修改數(shù)組后，返回數(shù)組可能的最大和。
示例 1：輸入：A = [4,2,3], K = 1
輸出：5
解釋：選擇索引 (1,) ，然后 A 變?yōu)?[4,-2,3]。
示例 2：
輸入：A = [3,-1,0,2], K = 3
輸出：6
解釋：選擇索引 (1, 2, 2) ，然后 A 變?yōu)?[3,1,0,2]。
示例 3：
輸入：A = [2,-3,-1,5,-4], K = 2
輸出：13
解釋：選擇索引 (1, 4) ，然后 A 變?yōu)?[2,3,-1,5,4]。
提示：
- 1 <= A.length <= 10000
- 1 <= K <= 10000
- -100 <= A[i] <= 100
思路
本題思路其實比較好想了，如何可以讓 數(shù)組和 最大呢?
貪心的思路，局部最優(yōu)：讓絕對值大的負(fù)數(shù)變?yōu)檎龜?shù)，當(dāng)前數(shù)值達(dá)到最大，整體最優(yōu)：整個數(shù)組和達(dá)到最大。
局部最優(yōu)可以推出全局最優(yōu)。
那么如果將負(fù)數(shù)都轉(zhuǎn)變?yōu)檎龜?shù)了，K依然大于0，此時的問題是一個有序正整數(shù)序列，如何轉(zhuǎn)變K次正負(fù)，讓 數(shù)組和 達(dá)到最大。
那么又是一個貪心：局部最優(yōu)：只找數(shù)值最小的正整數(shù)進(jìn)行反轉(zhuǎn)，當(dāng)前數(shù)值可以達(dá)到最大(例如正整數(shù)數(shù)組{5, 3, 1}，反轉(zhuǎn)1 得到-1 比 反轉(zhuǎn)5得到的-5 大多了)，全局最優(yōu)：整個 數(shù)組和 達(dá)到最大。
雖然這道題目大家做的時候，可能都不會去想什么貪心算法，一鼓作氣，就AC了。
「我這里其實是為了給大家展現(xiàn)出來 經(jīng)常被大家忽略的貪心思路，這么一道簡單題，就用了兩次貪心!」
那么本題的解題步驟為：
- 第一步：將數(shù)組按照絕對值大小從大到小排序，「注意要按照絕對值的大小」
- 第二步：從前向后遍歷，遇到負(fù)數(shù)將其變?yōu)檎龜?shù)，同時K--
- 第三步：如果K還大于0，那么反復(fù)轉(zhuǎn)變數(shù)值最小的元素，將K用完
- 第四步：求和
對應(yīng)C++代碼如下：
- class Solution {
- static bool cmp(int a, int b) {
- return abs(a) > abs(b);
- }
- public:
- int largestSumAfterKNegations(vector<int>& A, int K) {
- sort(A.begin(), A.end(), cmp); // 第一步
- for (int i = 0; i < A.size(); i++) { // 第二步
- if (A[i] < 0 && K > 0) {
- A[i] *= -1;
- K--;
- }
- }
- while (K--) A[A.size() - 1] *= -1; // 第三步
- int result = 0;
- for (int a : A) result += a; // 第四步
- return result;
- }
- };
總結(jié)
貪心的題目如果簡單起來，會讓人簡單到開始懷疑：本來不就應(yīng)該這么做么?這也算是算法?我認(rèn)為這不是貪心?
本題其實很簡單，不會貪心算法的同學(xué)都可以做出來，但是我還是全程用貪心的思路來講解。
因為貪心的思考方式一定要有!
「如果沒有貪心的思考方式(局部最優(yōu)，全局最優(yōu))，很容易陷入貪心簡單題憑感覺做，貪心難題直接不會做，其實這樣就鍛煉不了貪心的思考方式了」。
所以明知道是貪心簡單題，也要靠貪心的思考方式來解題，這樣對培養(yǎng)解題感覺很有幫助。
本文轉(zhuǎn)載自微信公眾號「代碼隨想錄」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系代碼隨想錄公眾號。
