題目

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

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

重復這個過程恰好 k 次。可以多次選擇同一個下標 i 。
以這種方式修改數組后，返回數組 可能的最大和 。

思路

這道題的關鍵點在于六個字：可以多次選擇！
所以我們想要獲得最大和我們就要在k還沒到0前先從小到大的把負數變為正數，然后就有兩種情況，k耗盡了或者是沒有負數了。這時候我們再分情況討論即可，如果k耗盡了那么最大和毋庸置疑就是當前數組的和，如果是沒有負數了那么面對全部都是正數的數組我們就再需要分情況討論了也就是當前k的值是偶數還奇數。如果k是偶數因為可以多次選擇一個位置來取得相反數也就是-1的偶次冪，也就是1那么答案還是當前數組的和，如果k是奇數那就是一個位置的值要變成相反數了。那么選擇哪個位置呢？當然是最小數。

代碼

class Solution {
public:int largestSumAfterKNegations(vector<int>& nums, int k) {int n = nums.size();int res = 0;// 按升序進行排序sort(nums.begin(), nums.end());for (int i = 0; i < n; i++) {// 如果有負數并且k大于0說明這個負數可以變成正數if (nums[i] < 0 && k > 0) {nums[i] = -nums[i];k--;}res += nums[i];}// 再排一次，讓最小的數排前面sort(nums.begin(), nums.end());if (k % 2 != 0) {// 如果k為奇數我們就要讓res加上最小數的相反數// 所以res等于加上兩倍的最小數，當然這個最小數不知道是正是負res += -1 * 2 * nums[0];}// 如果k為偶數那么res就不用動，因為可以多次相反// 偶數次就直接抵消了return res;}
};