LeetCode-Alg-1005-Maximize Sum Of Array After K Negations

LeetCode-Alg-1005-Maximize Sum Of Array After K Negations

Posted by Jae on June 20, 2019

1、题目

Given an array A of integers, we must modify the array in the following way: we choose an i and replace A[i] with -A[i], and we repeat this process K times in total. (We 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: A = [4,2,3], K = 1
Output: 5
Explanation: Choose indices (1,) and A becomes [4,-2,3].
Example 2:

Input: A = [3,-1,0,2], K = 3
Output: 6
Explanation: Choose indices (1, 2, 2) and A becomes [3,1,0,2].
Example 3:

Input: A = [2,-3,-1,5,-4], K = 2
Output: 13
Explanation: Choose indices (1, 4) and A becomes [2,3,-1,5,4].

Note:

1 <= A.length <= 10000
1 <= K <= 10000
-100 <= A[i] <= 100

2、思路

1）我们可以先对数组进行非降序排序，然后从前往后扫描，遇到负数消耗一次操作将其变为正数，遇到0将全部操作用在其上，此时数组取得最大值；

2）当遇到正数，如果K2的倍数，则两次操作后原数不变，如果K是奇数则可能需要将正数变为负数，但是这里有个问题，如果排序后的数组第一个元素就是正数， 取决于K%2的值，如果在其它位置遇到了正数，说明前面一个数一定是负数，此时不仅需要判断K%2的值，还要判断前一个数与当前数的大小，如果小于当前数则撤销前一个数的取反操作让当前K为偶数，这样就保证最终数组和是增加的。

3、实现

public class Solution {
public int largestSumAfterKNegations(int[] A, int K) {
Arrays.sort(A);
for (int i = 0; K > 0 && i < A.length; i++){
if (A[i] < 0){
A[i] = -A[i];
K--;
}else if (A[i] == 0){
break;
}else{
// 如果遇到正数且i!=0说明前面一定是个负数
if (i != 0 && K % 2== 1){
if (A[i-1] < A[i]){
A[i-1] = -A[i-1];
}else{
A[i] = -A[i];
}
}else{
A[i] = K % 2 == 0 ? A[i] : -A[i];
}
break;
}
}
int ans = 0;
for (int a : A){
ans += a;
}
return ans;
}
}

< script src = " / js / bootstrap.min.js " >