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

这道题给了一个整数数组,可能有正有负,然后给了一个正整数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 同步地址:

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


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation