一、題目
LeetCode-1005. K 次取反后最大化的數(shù)組和
地址：https://leetcode-cn.com/problems/maximize-sum-of-array-after-k-negations/
難度：簡單
給定一個整數(shù)數(shù)組 A刹帕，我們只能用以下方法修改該數(shù)組：我們選擇某個索引 i 并將 A[i] 替換為 -A[i]，然后總共重復這個過程 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ù)變成正數(shù)浑娜，盡可能的把最小的正數(shù)變?yōu)樨摂?shù)佑力，這樣數(shù)組的和最大。
那么代碼如何實現(xiàn)呢筋遭？先對數(shù)組排序打颤，把負數(shù)都變?yōu)檎龜?shù)（操作次數(shù)小于k）。再次排序漓滔，判斷剩下k次奇偶性瘸洛，如果是偶數(shù)，--得正次和；如果是正數(shù)把nums[0]（當前最小值）取反。
最后那伐，計算數(shù)組和即可踏施。
三、實現(xiàn)過程
c++
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
sort(nums.begin(),nums.end());
int i = 0;
while(k > 0 && nums[i] < 0){
nums[i] = -nums[i];
i++;
k--;
}
sort(nums.begin(),nums.end());
k = k % 2;
if(k == 1){
nums[0] *= -1;
}
int sum = 0;
for(int i = 0; i < nums.size();++i){
sum += nums[i];
}
return sum;
}
};
PHP
class Solution {
/**
* @param Integer[] $nums
* @param Integer $k
* @return Integer
*/
function largestSumAfterKNegations($nums, $k) {
sort($nums);
$i = 0;
while($k > 0 && $nums[$i] < 0){
$nums[$i] = -$nums[$i];
$i++;
$k--;
}
sort($nums);
$k = $k % 2;
if($k == 1){
$nums[0] = -$nums[0];
}
return array_sum($nums);
}
}
JavaScript
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var largestSumAfterKNegations = function(nums, k) {
nums.sort((a,b)=>a-b);
let i = 0;
while(k > 0 && nums[i] < 0){
nums[i] = -nums[i];
i++;
k--;
}
nums.sort((a,b)=>a-b);
k = k % 2;
if(k == 1){
nums[0] = -nums[0];
}
let sum = 0;
for(let i = 0;i < nums.length; ++i){
sum += nums[i];
}
return sum;
};
四罕邀、小結(jié)
本題的特點在于使用了兩次貪心策略畅形。
第一次，讓絕對值大的負數(shù)變?yōu)檎龜?shù)诉探。
如果將負數(shù)都轉(zhuǎn)變?yōu)檎龜?shù)了日熬，K依然大于0，如何轉(zhuǎn)變K次正負肾胯，讓數(shù)組和達到最大竖席。
第二次耘纱，只要找到數(shù)值最小的正整數(shù)進行反轉(zhuǎn)即可。
