https://leetcode-cn.com/problems/maximize-sum-of-array-after-k-negations/
给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个个索引 i 并将 A[i] 替换为 -A[i]，然后总共重复这个过程 K 次。（我们可以多次选择同一个索引 i。）
以这种方式修改数组后，返回数组可能的最大和。
示例 1：
输入：A = [4,2,3], K = 1
输出：5
解释：选择索引 (1,) ，然后 A 变为 [4,-2,3]。
示例 2：
输入：A = [3,-1,0,2], K = 3
输出：6
解释：选择索引 (1, 2, 2) ，然后 A 变为 [3,1,0,2]。
示例 3：
输入：A = [2,-3,-1,5,-4], K = 2
输出：13
解释：选择索引 (1, 4) ，然后 A 变为 [2,3,-1,5,4]。
提示：
1 <= A.length <= 10000
1 <= K <= 10000
-100 <= A[i] <= 100
小菜鸡的尝试：
通过样例的设计，研究出可分为以下几种情况：
1.操作次数大于负数个数
1）操作次数 - 负数个数 是偶数 全部的负数都可以转正
2）操作次数 - 负数个数 是奇数 绝对值最小的正数/负数 需要变成负数
2.操作次数小于负数个数（绝对值小的负数不能转正）
主要通过时间换空间的思想，使用优先队列将非正数和正数分别使用两个优先队列储存从小到大，从大到小的排序存储。
1 class Solution { 2 public: 3 int largestSumAfterKNegations(vector<int>& A, int K) { 4 priority_queue<int> a; // 记录负数 5 priority_queue<int, vector<int>, greater<int> > b; // 记录负数 6 priority_queue<int, vector<int>, greater<int> > c; // 记录正数 7 int result = 0; 8 for (int i = 0; i < A.size(); i ++) { 9 if (A[i] <= 0) { 10 b.push(A[i]); 11 a.push(A[i]); 12 } else { 13 c.push(A[i]); 14 } 15 } 16 cout << "K=" << K << endl; 17 cout << "非正元素的个数" << b.size() << endl; 18 if (K <= b.size()) { // 不一定所有负数都能转正 19 while (K) { // 加入转正的负数 20 result = result - b.top(); 21 b.pop(); 22 K--; 23 } 24 while (!b.empty()){ // 加入不能转正的负数 25 result = result + b.top(); 26 b.pop(); 27 } 28 while (!c.empty()) { //加入正数 29 result = result + c.top(); 30 c.pop(); 31 } 32 return result; 33 } 34 if (K > b.size()) { // 可能有正数要变负或者最小负数不能转正 35 if ((K - b.size()) % 2 == 0) { // 所有负数可变正数 36 cout << "1" << endl; 37 while (!b.empty()){ // 加入转正的负数 38 result = result - b.top(); 39 b.pop(); 40 } 41 while (!c.empty()) { //加入正数 42 result = result + c.top(); 43 c.pop(); 44 } 45 return result; 46 } 47 if ((K - b.size()) % 2 != 0) { // 可能有正数要变负或者最小负数不能转正 48 if (b.empty() || (-1 * a.top()) > c.top()) { // 最小正数要变负 49 result = result - c.top(); // 加入最小正数转负后的值 50 c.pop(); 51 while (!b.empty()){ // 加入转正的负数 52 result = result - b.top(); 53 b.pop(); 54 } 55 while (!c.empty()) { //加入正数 56 result = result + c.top(); 57 c.pop(); 58 } 59 return result; 60 } 61 if ((-1 * a.top()) <= c.top()) { // 最大负数不能转正 62 cout << "最大负数不能转正" << endl; 63 result = result + a.top(); // 加入最大负数 64 a.pop(); 65 while (!a.empty()){ // 加入转正的负数 66 result = result - a.top(); 67 a.pop(); 68 } 69 while (!c.empty()) { //加入正数 70 result = result + c.top(); 71 c.pop(); 72 } 73 return result; 74 } 75 76 } 77 } 78 return result; 79 } 80 };
小菜鸡做了一点点优化，在第一遍遍历压入优先队列的时候就计算所有数据的绝对值之和，而在分情况的时候在进行修正，可以略微减少时间消耗
1 class Solution { 2 public: 3 int largestSumAfterKNegations(vector<int>& A, int K) { 4 priority_queue<int> a; // 记录负数 5 priority_queue<int, vector<int>, greater<int> > b; // 记录负数 6 priority_queue<int, vector<int>, greater<int> > c; // 记录正数 7 priority_queue<int> d; // 记录正数 8 int result = 0; 9 for (int i = 0; i < A.size(); i ++) { 10 if (A[i] <= 0) { 11 b.push(A[i]); 12 a.push(A[i]); 13 result = result - A[i]; 14 } else { 15 c.push(A[i]); 16 d.push(A[i]); 17 result = result + A[i]; 18 } 19 } 20 cout << "K=" << K << endl; 21 cout << "非正元素的个数" << b.size() << endl; 22 if (K <= b.size()) { // 不一定所有负数都能转正 23 while (b.size() - K) { // 加入不能转正的负数 24 result = result + 2 * a.top(); 25 a.pop(); 26 K ++; 27 } 28 return result; 29 } 30 if (K > b.size()) { // 可能有正数要变负或者最小负数不能转正 31 if ((K - b.size()) % 2 == 0) { // 所有负数可变正数 32 return result; 33 } 34 if ((K - b.size()) % 2 != 0) { // 可能有正数要变负或者最小负数不能转正 35 if (b.empty() || (-1 * a.top()) > c.top()) { // 最小正数要变负 36 result = result - 2 * c.top(); // 加入最小正数转负后的值 37 return result; 38 } 39 if ((-1 * a.top()) <= c.top()) { // 最大负数不能转正 40 result = result + 2 * a.top(); // 加入最大负数 41 return result; 42 } 43 } 44 } 45 return result; 46 } 47 };
膜拜大佬的代码：
总体思路是一样的，他用sort方法直接对原数据进行改动，减去优先队列的空间开销。
1 int largestSumAfterKNegations(vector<int>& A, int K) { 2 sort(A.begin(),A.end()); // 用sort函数来替换优先队列的空间开销 3 if (A[0] >= 0) { // 最小正数 4 if (K % 2 != 0) A[0] = -A[0]; 5 return accumulate(A.begin(),A.end(),0); 6 } 7 for (int i = 0; i < K; i ++) { 8 // 非正数优先转正，越小越优先 9 if (A[i] < 0) { // 负数逐个转正 10 A[i] = -A[i]; 11 } else if (A[i] == 0) { 12 break; 13 // 正数的操作 14 } else { 15 if ((K-i) % 2 == 0) break; // 可以通过两次重复操作来消除 16 if (A[i] < A[i-1]) { 17 A[i] = -A[i]; 18 } else { 19 A[i-1] = -A[i-1]; 20 } 21 break; 22 } 23 } 24 return accumulate(A.begin(),A.end(),0); 25 }
还看见了一个相同思路但是表述更加简洁的一个操作
1 int largestSumAfterKNegations(vector<int> &A, int K) { 2 sort(A.begin(), A.end()); // 排序 3 int ans = 0; 4 for (int i = 0; i < A.size(); i++) { 5 if (A[i] < 0 && K > 0) { // 先尽可能将所有负数转正 6 A[i] = -A[i]; 7 K--; 8 } 9 } 10 sort(A.begin(), A.end()); // 转正后再排一次序 11 while (K > 0) { // 对转正后的最小的数进行操作 12 A[0] = -A[0]; 13 K--; 14 } 15 for (int i = 0; i < A.size(); i++) { // 做一次加法 16 ans += A[i]; 17 } 18 return ans; 19 }