Maximize Sum Of Array After K Negations using Greedy Algorithm v

  • 时间:2020-09-21 09:15:21
  • 分类:网络文摘
  • 阅读:83 次

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) —

推荐阅读:
求甲乙两车的速度  获纪念奖的有多少人?  程大位与剩余定理  “位数”和“数位”的意义为什么不同?  节约用水的资料  求发芽率、合格率、出粉率等百分率的公式中为什么都要乘100%?  为什么公历7月和8月都是31天  引流粉丝到公众号,网站运营的一点思考,引流技巧实操  站长如何赚钱?下面七条你做到了么?  个人站长成功的七条经验分享 
评论列表
添加评论