貪心算法之如何實現K次取反后最大化的數組和

本篇內容主要講解“貪心算法之如何實現K次取反后最大化的數組和”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“貪心算法之如何實現K次取反后最大化的數組和”吧!

很多錄友都反饋昨天的題目：貪心算法：跳躍游戲II  很難，這樣我就放心了，哈哈，因為我剛剛講解貪心的時候一些錄友會建議我：貪心沒有必要單獨講，直接講動規就可以了。應該不少同學都會感覺就貪心嘛，有啥難的。現在我們可以發現貪心的道理雖然簡單，但解決問題都很巧妙，難度上不照動規差多少。

今天是一道簡單題，關鍵在于培養貪心的解題思路!

給定一個整數數組 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]。

提示：

• 1 <= A.length <= 10000

• 1 <= K <= 10000

• -100 <= A[i] <= 100

思路

本題思路其實比較好想了，如何可以讓 數組和 最大呢?

貪心的思路，局部最優：讓絕對值大的負數變為正數，當前數值達到最大，整體最優：整個數組和達到最大。

局部最優可以推出全局最優。

那么如果將負數都轉變為正數了，K依然大于0，此時的問題是一個有序正整數序列，如何轉變K次正負，讓 數組和 達到最大。

那么又是一個貪心：局部最優：只找數值最小的正整數進行反轉，當前數值可以達到最大(例如正整數數組{5, 3, 1}，反轉1 得到-1 比 反轉5得到的-5  大多了)，全局最優：整個 數組和 達到最大。

雖然這道題目大家做的時候，可能都不會去想什么貪心算法，一鼓作氣，就AC了。

「我這里其實是為了給大家展現出來 經常被大家忽略的貪心思路，這么一道簡單題，就用了兩次貪心!」

那么本題的解題步驟為：

• 第一步：將數組按照絕對值大小從大到小排序，「注意要按照絕對值的大小」

• 第二步：從前向后遍歷，遇到負數將其變為正數，同時K--

• 第三步：如果K還大于0，那么反復轉變數值最小的元素，將K用完

• 第四步：求和

對應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;     } };

到此，相信大家對“貪心算法之如何實現K次取反后最大化的數組和”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！