代码随想录算法训练营第二十八天| 1005.K次取反后最大化的数组和 134. 加油站 135. 分发糖果 -526互联

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

思路：

仅排序一次，当前数<下一个数，就反转当前数，如果大于，那么就反转下一个 ——》也就是保证每次反转都是最小的数

注意：如果移动到最后一个节点了，K还没用完，那么就证明只能反转K

代码：

 1 int largestSumAfterKNegations(vector<int>& nums, int k) {
 2     if (nums.size() == 0) return 0;
 3     sort(nums.begin(), nums.end());
 4 
 5     int i = 0;
 6     //可能存在最后一个数为最小数
 7     while ( k > 0)
 8     {
 9         //如果到最后一个数了，K还没用完，就证明只能修改最后一个数
10         if (i == nums.size() - 1)
11         {
12             nums[i] = -nums[i];
13             k--;
14             continue;
15         }
16         //这个只能保证当前数是不是小数，
17         if (i < nums.size() - 1 && nums[i] <= nums[i + 1])
18         {
19             nums[i] = -nums[i];
20             k--;
21         }
22         else
23         {
24             i++;
25         }
26         
27     }
28 
29     int result = 0;
30     for (int j = 0; j < nums.size(); j++)
31     {
32         result += nums[j];
33     }
34 
35     return result;
36 }