# 1005. Maximize Sum Of Array After K Negations

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. `1 <= A.length <= 10000`
2. `1 <= K <= 10000`
3. `-100 <= A[i] <= 100`

``````class Solution {
public:
int largestSumAfterKNegations(vector<int>& A, int K) {
int res = 0, n = A.size(), mn = INT_MAX;
priority_queue<int> q;
for (int num : A) {
if (num < 0) q.push(-num);
res += num;
mn = min(mn, abs(num));
}
while (!q.empty() && K > 0) {
res += q.top() * 2; q.pop();
--K;
}
return res - (K % 2) * 2 * mn;
}
};
``````

``````class Solution {
public:
int largestSumAfterKNegations(vector<int>& A, int K) {
int res = 0, n = A.size(), mn = INT_MAX;
sort(A.begin(), A.end());
for (int i = 0; i < n && K > 0 && A[i] < 0; ++i, --K) {
A[i] = -A[i];
}
for (int num : A) {
res += num;
mn = min(mn, num);
}
return res - (K % 2) * 2 * mn;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1005

https://leetcode.com/problems/maximize-sum-of-array-after-k-negations/

https://leetcode.com/problems/maximize-sum-of-array-after-k-negations/discuss/252254/JavaC%2B%2BPython-Sort

https://leetcode.com/problems/maximize-sum-of-array-after-k-negations/discuss/252228/A-very-simple-java-solution

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation