1005. K 次取反后最大化的数组和

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 };

 

 

 

 

上一篇:equals()和hashCode()隐式调用时的约定


下一篇:数据结构与算法(Python版)二:大 O 表示法