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

推荐阅读:
男生人数的40%比女生人数的一半还多3人  某工厂一、二车间共360人  将侧面积是94.2平方厘米的圆柱拼成一个近似的长方体  公交车共有多少张座位?  新华书店运来书600本  这艘轮船最多驶出多远就应返回  两个完全相同的长方体恰好拼成一个正方体  从右往左数,小兰排在第几个?  网站安全公司对个人隐私保护措施  网站渗透测试行业中需要文凭吗 
评论列表
添加评论