[LeetCode] 1005. Maximize Sum Of Array After K Negations

[grandyang]

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

这道题给了一个整数数组，可能有正有负，然后给了一个正整数K，说是可以进行K次操作，每次操作是可以将任意位置的上的数字翻转成其的相反数，即正数变负数，或者负数变正数，并且同一个位置上的数字可以进行多次变换，现在问经过K次变换后，返回最大的数组之和。首先来想，怎么使得数组和最大，肯定是正数越多越好，如果数组中有负数，肯定是要将其变为正数，此时数组中负数的个数和K之间的大小关系并不确定，所以需要分情况来讨论。当然最简单的情况就是负数的个数正好等于K，这样只要将所有的负数都变成正数，就可以了。若负数的个数大于K，则肯定是选最小的K个，也就是绝对值最大的K个，这样翻转后和才能最大。若负数个数小于K，此时都翻转成了正数，但是K值还没用完，还是要翻转，此时要分K的奇偶来讨论，由于同一个位置可以多次翻转，若K是偶数，则每次翻转后都可以翻回去，没有任何影响，而若K是奇数，则必定会有一个非负数会被翻转，那肯定希望翻转的是最小的非负数，从而对结果影响最小。分析到这，基本上整个解题思路就有了，使用一个优先队列来记录所有的负数的绝对值，再用一个变量 mn 来记录数组中绝对值最小的数字，遍历数组，若遇到负数，则将其对应的正数排入优先队列，然后每次将这个数字加入结果 res，并且更新绝对值最小的数字。之后进行遍历，遍历的次数是负数的个数和K之间的较小值，每次取出绝对值最大的负数，将其绝对值乘以2并加入到结果 res 中。循环结束后，K的值可能或奇或偶，当K是偶数的时候（包括0），直接返回 res，若是奇数的话，要减去 mn 的2倍，这是数组中绝对值最小的数，参见代码如下：

解法一：

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;
    }
};

我们也可以不用优先队列，而是先给数组排个序，这样所有的负数都在数组的前面了，然后此时将前K个负数翻转成正数，注意只是翻转负数，若负数的个数小于K，也不会翻转多余的正数。然后此时遍历数组，求数组之后，并且求此时数组中最小的数字，此时K还是有奇偶两种情况，当K是偶数的时候（包括0），直接返回数组之和，若是奇数的时候，此时说明数组中的负数已经全部翻转为了正数，那么最小的数也就是绝对值最小的数，减去其的2倍即可，参见代码如下：

解法二：

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 同步地址:

#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 题目讲解汇总(持续更新中...)