Maximize Sum Of Array After K Negations
Given an integer array nums and an integer k, modify the array in the following way:
choose an index i and replace nums[i] with -nums[i].
You should apply this process exactly k times. You may choose the same index i multiple times.
Return the largest possible sum of the array after modifying it in this way.
Example 1:
Input: nums = [4,2,3], k = 1
Output: 5
Explanation: Choose index 1 and nums becomes [4,-2,3].
Example 2:
Input: nums = [3,-1,0,2], k = 3
Output: 6
Explanation: Choose indices (1, 2, 2) and nums becomes [3,1,0,2].
Example 3:
Input: nums = [2,-3,-1,5,-4], k = 2
Output: 13
Explanation: Choose indices (1, 4) and nums becomes [2,3,-1,5,4].
思路一：先找 k 个最小的数字，然后把负数取反，如果还剩余取反次数，把绝对值最小的数字取反，最后统计
public int largestSumAfterKNegations(int[] nums, int k) {
for (int i = 0; i < nums.length && i < k; i++) {
for (int j = 0; j < nums.length - 1; j++) {
if (nums[j] < nums[j+1]) {
int temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
}
}
}
int idx = nums.length - 1;
while (k > 0 && idx >= 0 && nums[idx] < 0) {
nums[idx] = -nums[idx];
k--;
idx--;
}
if (k > 0 && (k & 1) == 1) {
//find index of min abs val in nums array
int minIdx = 0;
for (int i = 0; i < nums.length; i++) {
if (Math.abs(nums[i]) < Math.abs(nums[minIdx])) {
minIdx = i;
}
}
nums[minIdx] = -nums[minIdx];
}
return Arrays.stream(nums).sum();
}