題目

1005 K 次取反后最大化的數組和

給你一個整數數組 nums 和一個整數 k ，按以下方法修改該數組：

選擇某個下標 i 并將 nums[i] 替換為 -nums[i] 。

重復這個過程恰好 k 次。可以多次選擇同一個下標 i 。

以這種方式修改數組后，返回數組 可能的最大和 。

示例 1：

輸入：nums = [4,2,3], k = 1

輸出：5

解釋：選擇下標 1 ，nums 變為 [4,-2,3] 。

示例 2：

輸入：nums = [3,-1,0,2], k = 3

輸出：6

解釋：選擇下標 (1, 2, 2) ，nums 變為 [3,1,0,2] 。

示例 3：

輸入：nums = [2,-3,-1,5,-4], k = 2

輸出：13

解釋：選擇下標 (1, 4) ，nums 變為 [2,3,-1,5,4] 。

來源：力扣1005. K 次取反后最大化的數組和

---

思路（注意事項）

思路一：建立小根堆，每次修改堆頂（即最小值）。
思路二：貪心（條件排序）

---

純代碼1

class Solution {
public:int largestSumAfterKNegations(vector<int>& nums, int k) {priority_queue<int, vector<int>, greater<int>> q;for (int i = 0; i < nums.size() ; i ++) q.push(nums[i]);int ans = 0;for (int i = 0 ;i < k; i ++){int t = - q.top();q.pop();q.push(t);}while(!q.empty()) ans += q.top(), q.pop();return ans;}
};

題解1（加注釋）

class Solution {
public:int largestSumAfterKNegations(vector<int>& nums, int k) {// 定義一個最小堆（優先隊列），用于存儲數組中的元素priority_queue<int, vector<int>, greater<int>> q;// 將數組中的所有元素放入最小堆for (int i = 0; i < nums.size(); i++) q.push(nums[i]);// ans 用于存儲最終的累加和int ans = 0;// 進行 k 次取反操作for (int i = 0; i < k; i++) {// 取出堆頂元素（當前最小的元素）int t = -q.top();// 將堆頂元素彈出q.pop();// 將取反后的元素重新放入堆中q.push(t);}// 計算堆中所有元素的和while (!q.empty()) {ans += q.top(); // 取出堆頂元素并累加到 ansq.pop();        // 彈出堆頂元素}// 返回最終的累加和return ans;}
};

純代碼2

class Solution {
static bool cmp (int a, int b)
{return abs(a) > abs(b);
}
public:int largestSumAfterKNegations(vector<int>& nums, int k) {sort (nums.begin(), nums.end(), cmp);int ans = 0;for (int i = 0; i < nums.size() && k > 0; i ++)if (nums[i] < 0) nums[i] = - nums[i], k --;if (k % 2 == 1) nums[nums.size() - 1] *= -1;for (auto i : nums) ans += i;return ans;}
};

題解2（加注釋）

#include <vector>
#include <algorithm>
#include <cmath>class Solution {// 自定義比較函數，用于 std::sort 排序// 該函數的作用是按照絕對值從大到小對元素進行排序static bool cmp (int a, int b){// 返回絕對值大的元素排在前面return abs(a) > abs(b);}
public:// 該函數用于計算經過 k 次取反操作后數組元素的最大和int largestSumAfterKNegations(vector<int>& nums, int k) {// 使用自定義的 cmp 函數對數組進行排序，使得絕對值大的元素排在前面sort (nums.begin(), nums.end(), cmp);// 用于存儲最終的數組元素和int ans = 0;// 遍歷數組，優先將絕對值大的負數取反for (int i = 0; i < nums.size() && k > 0; i ++) {// 如果當前元素是負數，將其取反，并將 k 減 1if (nums[i] < 0) {nums[i] = - nums[i];k --;}}// 如果 k 還有剩余且為奇數，說明還需要進行一次取反操作// 此時對絕對值最小的元素進行取反，因為前面已經按絕對值從大到小排序，所以最后一個元素絕對值最小if (k % 2 == 1) {nums[nums.size() - 1] *= -1;}// 遍歷數組，計算所有元素的和for (auto i : nums) {ans += i;}// 返回最終的和return ans;}
};