1005. Maximize Sum Of Array After K Negations

1005. Maximize Sum Of Array After K Negations (Easy)

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

Related Topics:
Greedy

Solution 1.

// OJ: https://leetcode.com/problems/maximize-sum-of-array-after-k-negations/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    int largestSumAfterKNegations(vector<int>& A, int K) {
        sort(begin(A), end(A));
        int sum = 0, i = 0;
        for (; K > 0 && i < A.size() && A[i] < 0; ++i, --K) sum += -A[i];
        if (K % 2 && (i == A.size() || A[i] != 0)) {
            if (i == 0) sum -= A[i];
            else if (i == A.size()) sum += 2 * A[i - 1];
            else if (-A[i - 1] < A[i]) sum += 2 * A[i - 1] + A[i];
            else sum -= A[i];
            ++i;
        }
        for (; i < A.size(); ++i) sum += A[i];
        return sum;
    }
};