很多錄友都反饋昨天的題目: 很難,這樣我就放心了,哈哈,因為我剛剛講解貪心的時候一些錄友會建議我:貪心沒有必要單獨講,直接講動規就可以了。應該不少同學都會感覺就貪心嘛,有啥難的。現在我們可以發現貪心的道理雖然簡單,但解決問題都很巧妙,難度上不照動規差多少。
今天是一道簡單題,關鍵在於培養貪心的解題思路!
題目地址: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]。
提示:
本題思路其實比較好想了,如何可以讓 數組和 最大呢?
貪心的思路,局部最優:讓絕對值大的負數變為正數,當前數值達到最大,整體最優:整個數組和達到最大。
局部最優可以推出全局最優。
那麼如果將負數都轉變為正數了,K依然大於0,此時的問題是一個有序正整數序列,如何轉變K次正負,讓 數組和 達到最大。
那麼又是一個貪心:局部最優:只找數值最小的正整數進行反轉,當前數值可以達到最大(例如正整數數組{5, 3, 1},反轉1 得到-1 比 反轉5得到的-5 大多了),全局最優:整個 數組和 達到最大。
雖然這道題目大家做的時候,可能都不會去想什麼貪心算法,一鼓作氣,就AC了。
「我這裡其實是為了給大家展現出來 經常被大家忽略的貪心思路,這麼一道簡單題,就用了兩次貪心!」
那麼本題的解題步驟為:
對應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; }};
貪心的題目如果簡單起來,會讓人簡單到開始懷疑:本來不就應該這麼做麼?這也算是算法?我認為這不是貪心?
本題其實很簡單,不會貪心算法的同學都可以做出來,但是我還是全程用貪心的思路來講解。
因為貪心的思考方式一定要有!
「如果沒有貪心的思考方式(局部最優,全局最優),很容易陷入貪心簡單題憑感覺做,貪心難題直接不會做,其實這樣就鍛鍊不了貪心的思考方式了」。
所以明知道是貪心簡單題,也要靠貪心的思考方式來解題,這樣對培養解題感覺很有幫助。
此時,有沒有感覺Carl為了給大家寫出優質的題解真的是煞費苦心啊!!哈哈,還不趕緊幫忙宣傳一波「代碼隨想錄」,讓更多的小夥伴知道這裡,這樣Carl也更有動力寫下去呀![加油]
打算從頭開始打卡的錄友,可以在「算法匯總」這裡找到歷史文章,很多錄友都在從頭打卡,你並不孤單!
-------end-------
我將算法學習相關的資料已經整理到了Github :https://github.com/youngyangyang04/leetcode-master,裡面還有leetcode刷題攻略、各個類型經典題目刷題順序、思維導圖看一看一定會有所收穫,如果給你有幫助給一個star支持一下吧!
我是程式設計師Carl,個人主頁:https://github.com/youngyangyang04
更多精彩點擊下方了解更多!