【刷题】代码随想录算法训练营第三十三天|1005、K次取反后最大化的数组和，134、加油站，135、分发糖果

本文主要是介绍【刷题】代码随想录算法训练营第三十三天|1005、K次取反后最大化的数组和，134、加油站，135、分发糖果，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

讲解：https://programmercarl.com/1005.K%E6%AC%A1%E5%8F%96%E5%8F%8D%E5%90%8E%E6%9C%80%E5%A4%A7%E5%8C%96%E7%9A%84%E6%95%B0%E7%BB%84%E5%92%8C.html

关键：绝对值排序

class Solution {
public:static bool cmp(int a, int b) {return abs(a) > abs(b);
}int largestSumAfterKNegations(vector<int>& nums, int k) {sort(nums.begin(), nums.end(), cmp);for (int i=0; i< nums.size();i++){if(nums[i] < 0 && k > 0) {nums[i] *= -1;k--;}}if (k % 2 == 1) nums[nums.size() -1 ] *= -1;int result =0;for (int a:nums) result+=a;return result;}
};

134、加油站

讲解：https://programmercarl.com/0134.%E5%8A%A0%E6%B2%B9%E7%AB%99.html

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int curSum = 0;int totalSum = 0;int start = 0;for (int i = 0; i<gas.size(); i++){curSum += gas[i] - cost[i];totalSum += gas[i] - cost[i];if (curSum < 0){start = i+1;curSum = 0;}}if (totalSum < 0) return -1;return start;}
};

135、分发糖果

讲解：https://programmercarl.com/0135.%E5%88%86%E5%8F%91%E7%B3%96%E6%9E%9C.html

从前到后和从后到钱两遍贪心遍历。

class Solution {
public:int candy(vector<int>& ratings) {vector<int> candyVec(ratings.size(), 1);for (int i=1; i < ratings.size(); i++){if (ratings[i-1] < ratings[i]) candyVec[i] = candyVec[i-1] +1;}for (int i=ratings.size()-1; i>0;i--){if (ratings[i-1]>ratings[i]) candyVec[i-1] = max(candyVec[i-1], candyVec[i]+1);}int result = 0;for (int r:candyVec) result+=r;return result;}
};