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

Greedy Algorithm Using Priority Queue

The Greedy algorithm works by selecting the optimal step at each iteration, which builds up the global optimal solution. We can always select the minimal value and negate it. By this approach, we can achieve the optimial.

The implementation can be based on priority queue. We push all the numbers to the priority queue, and at each iteration, we pop one (which is the minimal) and push its negated version back to the queue.

When K operations are finished, we pop all elements from the priority queue and sum them, which is the answer (maximum sum of array after K negations)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& A, int K) {
        priority_queue<int, vector<int>, std::greater<int>> pq;
        for (const auto &n: A) {
            pq.push(n);
        }
        for (int i = 0; i < K; ++ i) {
            auto p = pq.top();
            pq.pop();
            pq.push(-p);
        }
        int s = 0;
        while (!pq.empty()) {
            auto p = pq.top();
            s += p;
            pq.pop();
        }
        return s;
    }
};

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& A, int K) {
        priority_queue<int, vector<int>, std::greater<int>> pq;
        for (const auto &n: A) {
            pq.push(n);
        }
        for (int i = 0; i < K; ++ i) {
            auto p = pq.top();
            pq.pop();
            pq.push(-p);
        }
        int s = 0;
        while (!pq.empty()) {
            auto p = pq.top();
            s += p;
            pq.pop();
        }
        return s;
    }
};

The time complexity is O(T.LogT) where T is Max(N, K). The space complexity is O(N) where N is the size of A. Pushing an element to a priority queue takes O(logN) complexity.

Greedy Algorithm using min_element

The above same algorithm can be implemented using the min_element() which returns the minimal element between two iterators. Then, we can use modern C++ std::accumulate to get the sum.

1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& A, int K) {
        for (int i = 0; i < K; ++ i) {
            int m = min_element(begin(A), end(A)) - begin(A);
            A[m] *= -1;
        }
        return std::accumulate(begin(A), end(A), 0, 
                [](auto &a, auto &b) { return a + b; });
    }
};

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& A, int K) {
        for (int i = 0; i < K; ++ i) {
            int m = min_element(begin(A), end(A)) - begin(A);
            A[m] *= -1;
        }
        return std::accumulate(begin(A), end(A), 0, 
                [](auto &a, auto &b) { return a + b; });
    }
};

The C++ min_element() takes O(N) and thus the overall time complexity is O(MN). However, it has O(1) constant space usage.

–EOF (The Ultimate Computing & Technology Blog) —