[LeetCode]1005. K次取反后最大化的数组和
题目
给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
- 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
以这种方式修改数组后，返回数组 可能的最大和 。
示例
-
示例一
输入：nums = [4,2,3], k = 1
输出：5
解释：选择下标 1 ，nums 变为 [4,-2,3] 。 -
示例二
输入：nums = [3,-1,0,2], k = 3
输出：6
解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。 -
示例三
输入：nums = [2,-3,-1,5,-4], k = 2
输出：13
解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。
方法
从小到大修改负数
class Solution {
public int largestSumAfterKNegations(int[] nums, int k) {
int ans = 0;
int n = nums.length;
Arrays.sort(nums);
int cur = k;
for(int i=0;i<n;i++){
if(nums[i] < 0 && cur > 0){
nums[i] = -nums[i];
cur--;
}else{
break;
}
}
Arrays.sort(nums);
if(cur == 0){
for(int i=0;i<n;i++){
ans += nums[i];
}
return ans;
}else{
if( cur % 2 ==0){
for(int i=0;i<n;i++){
ans += nums[i];
}
return ans;
}else{
nums[0] = -nums[0];
for(int i=0;i<n;i++){
ans += nums[i];
}
return ans;
}
}
}
}
1 先将nums数组从小到大排序。
2 从下标0开始，将负数变为正数，直到没有负数或者次数用尽。
3 对取反完的数组再次排序。
4 若取反次数用尽，则直接求数组和。
5 若取反次数没用尽，说明数组内无负数。
6 由于可对一个下标重复取反，则剩余次数为偶数时，可以看作数组不变。
7 若剩余次数为奇数，则选择将最小的数取反，由于已排序，则取nums[0]。
8 求和返回答案。
注意
- cur用来记录对数组内负数取反行为结束后，还剩多少取反次数。
- 第二次排序是为了防止原数组中的负数取反后成为新的最小正数时无法定位。