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

这题给一个数组，还有一个K，我们必须变换某个数字的正负值K次，该如何操作才能使得总和最大。

这题得想明白才好做，不然做不好。我的思路如下：

1. 遍历一次数组，算出总和，同时找出最小的正整数，找不着也没关系。同时也要找出一个负数的数组，并进行排序
2. 将K次全部用于负数变为正数，这时候也要同时更新当前最小的正整数
3. 当K比负数数组小或者相等，那么直接结束了，我们只要尽量的把负变正已经把总和扩大了
4. 当K比负数的数量还大，我们首先对其对2取余，对一个正数变换两次等于没变换，我们在这里要尽量少的去操作，所以我们可知最多需要变换一个正数，而这个正数就是之前我们记录下来的最小正整数
5. 将最小正整数从和中减去即可

class MaximizeSumOfArrayAfterKNegations : public Solution {
    public:
    void Execute() {
        std::cout << "Case 1: " << largestSumAfterKNegations(vector<int>{-1, -2, -3}, 8);
    }
    int largestSumAfterKNegations(const vector<int>& A, int K) {
        int sum = 0;
        int posMin = A[0];
        vector<int> negs;
        for (auto v : A) {
            sum += v;
            if (v < 0) {
                negs.push_back(v);
            } else if (v < posMin || (v >= 0 && posMin < 0)) {
                posMin = v;
            }
        }
        std::sort(negs.begin(), negs.end());

        int negi = 0;
        while (K > 0 && negi < negs.size()) {
            sum += (2 * -negs[negi++]);
            K--;
            if (-negs[negi - 1] < posMin || (-negs[negi - 1] >= 0 && posMin < 0)) {
                posMin = -negs[negi - 1];
            }
        }
        if ((K % 2) != 0) {
            // Minus the smallest element
            sum -= posMin * 2;
        }
        return sum;
    }
};

这种解法速度还不错，超过了99.66%的解法