1005. K 次取反后最大化的數(shù)組和
題意：給你一個整數(shù)數(shù)組 nums 和一個整數(shù) k ，按以下方法修改該數(shù)組：
選擇某個下標(biāo) i 并將 nums[i] 替換為 -nums[i] 。
重復(fù)這個過程恰好 k 次孵滞⊙嚎颍可以多次選擇同一個下標(biāo) i 房匆。
以這種方式修改數(shù)組后，返回數(shù)組 可能的最大和 。
解題思路
解法1：
1.將nums分為兩個數(shù)組，正數(shù)數(shù)組和負(fù)數(shù)數(shù)組
2.將負(fù)數(shù)數(shù)組排序奴璃，優(yōu)先將負(fù)數(shù)數(shù)組處理k個，轉(zhuǎn)換為正數(shù)城豁，并且加入正數(shù)數(shù)組苟穆，同時需要從負(fù)數(shù)數(shù)組中移除
3.此時將正數(shù)數(shù)組，重新排序唱星，將最小的正數(shù)（即第一個正數(shù)）取k%2次反雳旅，然后求和即可
解法2：
1.基于原數(shù)組去操作，相同的思想间聊，先對nums排序攒盈，盡可能（k有可能大于負(fù)數(shù)個數(shù)，此時不再取反）的取反前面的k個負(fù)數(shù)
2.對nums排序哎榴，如果k依然有剩余型豁，則將第一個元素取k%2次反，然后求和即可
解題遇到的問題
無
后續(xù)需要總結(jié)學(xué)習(xí)的知識點(diǎn)
無
##解法1
import java.util.Collections;
import java.util.LinkedList;
class Solution {
public int largestSumAfterKNegations(int[] nums, int k) {
// 將nums分為兩個數(shù)組叹话，正數(shù)數(shù)組和負(fù)數(shù)數(shù)組
// 優(yōu)先將負(fù)數(shù)數(shù)組處理k個偷遗，轉(zhuǎn)換為正數(shù)，并且加入正數(shù)數(shù)組
// 如果k此時等于0驼壶，則此時數(shù)組元素之和氏豌，即為最大和
// 如果k此時依然大于0，則此時將正數(shù)數(shù)組热凹，重新排序泵喘，將最小的正數(shù)取k%2次反泪电，然后求和即可
LinkedList<Integer> bigArrayList = new LinkedList<Integer>();
LinkedList<Integer> smArrayList = new LinkedList<Integer>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] >= 0) {
bigArrayList.add(nums[i]);
} else {
smArrayList.add(nums[i]);
}
}
Collections.sort(smArrayList);
long ans = 0;
if (smArrayList.size() >= k) {
for (int i = 0; i < k; i++) {
bigArrayList.add(-smArrayList.get(0));
smArrayList.removeFirst();
}
} else {
for (int i = 0; i < smArrayList.size(); i++) {
bigArrayList.add(-smArrayList.get(i));
}
k = k - smArrayList.size();
smArrayList.clear();
Collections.sort(bigArrayList);
if (bigArrayList.size() > 0) {
bigArrayList.set(0,
k % 2 == 0
? bigArrayList.get(0)
: -bigArrayList.get(0));
}
}
for (int i = 0; i < bigArrayList.size(); i++) {
ans += bigArrayList.get(i);
}
for (int i = 0; i < smArrayList.size(); i++) {
ans += smArrayList.get(i);
}
return (int) ans;
}
}
##解法2：
class Solution {
public int largestSumAfterKNegations(int[] nums, int k) {
// 排序，把可能有的負(fù)數(shù)排到前面
Arrays.sort(nums);
int sum = 0;
for (int i = 0; i < nums.length; i++) {
// 貪心：如果是負(fù)數(shù)纪铺，而k還有盈余相速，就把負(fù)數(shù)反過來
if (nums[i] < 0 && k > 0) {
nums[i] = -1 * nums[i];
k--;
}
sum += nums[i];
}
Arrays.sort(nums);
// 如果k沒剩，那說明能轉(zhuǎn)的負(fù)數(shù)都轉(zhuǎn)正了鲜锚，已經(jīng)是最大和突诬，返回sum
// 如果k有剩，說明負(fù)數(shù)已經(jīng)全部轉(zhuǎn)正芜繁，所以如果k還剩偶數(shù)個就自己抵消掉旺隙，不用刪減，如果k還剩奇數(shù)個就減掉2倍最小正數(shù)骏令。
return sum - (k % 2 == 0 ? 0 : 2 * nums[0]);
}
}
