1005. K 次取反后最大化的数组和
描述：
给定一个整数数组 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:96 ms 8.6 MB
2 class Solution {
3 public:
4 int largestSumAfterKNegations(vector<int>& A, int K) {
5 /*思路：
6 数组 里面的数值可能有正 ，负 ,k次取反，
7 先对数组从小大排序，负数在前，正数在后，
8 1:如果数组里面的负数，
9 1.1负数的个数>=K ，那么可以负数取反k次,最后求和
10 1.2如果负数的个数<k,那么将负数的个数m 全部取反后，剩余k-m次，
11 1.3重新，排序，因为原先的负数 变成正的了，可能更小 如 -10,-1,4,5,
12 -1 变成1，那么，最小，所以重新排序
13 然后对第一个非负数进行操作，因为可以多次选择同一个索引 i。
14 1.4也可以不排序，定义一个变量 代表当前最小值
15 若(k-m)%2==0; 那么，第一个非负数为正，然后求和
16 若(k-m)%2==1 那么，第一个非负数为负，然后求和
17 2:若全为正数，排序，只对第一个 非负数进行操作k次 ，然后求和
18 */
19 sort(A.begin(),A.end());
20 int cnt=0;
21
22 for(int i=0;i<A.size();i++){
23 if(cnt==K) break;
24 if(A[i]<0&&cnt<K){
25 A[i]=-A[i];
26 cnt++;
27 }else{
28 sort(A.begin(),A.end());
29 if((K-cnt)%2!=0){//A[0]最小
30 A[0]=-A[0];
31
32 }
33 break;
34 }
35 }
36 int sum=0;
37 for(int i=0;i<A.size();i++){
38 sum+=A[i];
39 }
40 return sum;
41 }
42 };
1 解法2： 4 ms 8.7 MB
2 class Solution {
3 public:
4 int largestSumAfterKNegations(vector<int>& A, int K) {
5 /*思路：
6 数组 里面的数值可能有正 ，负 ,k次取反，
7 先对数组从小大排序，负数在前，正数在后，
8 1:如果数组里面的负数，
9 1.1负数的个数>=K ，那么可以负数取反k次,最后求和
10 1.2如果负数的个数<k,那么将负数的个数m 全部取反后，剩余k-m次，
11 1.3重新，排序，因为原先的负数 变成正的了，可能更小 如 -10,-1,4,5,
12 -1 变成1，那么，最小，所以重新排序
13 然后对第一个非负数进行操作，因为可以多次选择同一个索引 i。
14 1.4也可以不排序，定义一个变量 代表当前最小值
15 若(k-m)%2==0; 那么，第一个非负数为正，然后求和
16 若(k-m)%2==1 那么，第一个非负数为负，然后求和
17 2:若全为正数，排序，只对第一个 非负数进行操作k次 ，然后求和
18 */
19 sort(A.begin(),A.end());
20 int cnt=0;
21 int Min=INT_MAX,id=0;//记录一个最小值，和要进行修改的下标
22 for(int i=0;i<A.size();i++){
23 if(cnt==K) break;
24 if(A[i]<0&&cnt<K){
25 A[i]=-A[i];
26 cnt++;
27 if(Min>A[i]){//更新最小值和下标
28 Min=A[i];
29 id=i;
30 }
31 }else{ //sort(A.begin(),A.end());
32 if((K-cnt)%2!=0){//负数变成正数的最小值和 原来就非负 的第一个最小值进行比较
33 if(Min<A[i]) A[id]=-A[id];//看谁最小
34 else A[i]=-A[i];
35 }
36 break;
37 }
38 }
39 int sum=0;
40 for(int i=0;i<A.size();i++){
41 sum+=A[i];
42 }
43 return sum;
44 }
45 };