Day34 | 1005.K次取反后最大化的数组和, 134. 加油站, 135. 分发糖果
K次取反后最大化的数组和
LeetCode题目：https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/
整体思路
首先对数组进行排序，由于存在负值，很容易得出数组开始如果存在负数的话，取反负数收益最大。如果负数取反结束，或者数组本身就只有整数，那么只对最小值取反的风险最小。
class Solution {
public:int largestSumAfterKNegations(vector<int>& nums, int k) {sort(nums.begin(),nums.end());int i=0;while(k){if(nums[i]<0&&i<nums.size()-1){nums[i] = 0 - nums[i];i++;k--;continue;}if(i>0&&nums[i-1]<nums[i]){nums[i-1] = 0 - nums[i-1];k--;}else{nums[i] = 0 - nums[i];k--;}}int sum=0;for(int i=0;i<nums.size();i++){sum+=nums[i];}return sum;}
};
加油站
LeetCode题目：https://leetcode.cn/problems/gas-station/
解题思路
加油站问题首先需要明确两个定义：（1）如果循环一圈的总油耗大于总加油量，那么一定无法完成一次循环。（2）如果条件一满足，到达一个位置的时候，剩余油量为负数，则说明从开始到该点均不能作为起始点，起始点应该作为该位置的下一个位置。
代码如下：
class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int startIndex = 0,currSum=0,totalSum=0;for(int i = 0;i<gas.size();i++){currSum+=(gas[i]-cost[i]);totalSum+=(gas[i]-cost[i]);if(currSum<0){startIndex = i+1;currSum=0;}}if(totalSum<0) return -1;return startIndex;}
};
分发糖果
LeetCode题目：https://leetcode.cn/problems/candy/
解题思路
当一个贪心问题需要考虑两个方向的的得失收益时候，一定要先考虑完一边再说另一边！！！
因此，根据上述原则，我们可以先考虑只看每个孩子的左侧孩子分数（从左侧开始看是因为循环遍历时，可以先对0位置赋值。如果看右侧孩子，则第一个要从最右侧开始），如果大于左侧孩子，则糖果数量要比左孩子+1，否则给最少的糖果。
在一次遍历以后，每个孩子针对左侧孩子的糖果个数已经确定，此时要确定右侧孩子的对比，此时，如果右侧孩子的分数小于自身，则自身应当是右侧孩子糖果个数+1。否则不改变。
代码如下：
class Solution {
public:int candy(vector<int>& ratings) {vector<int> candies(ratings.size(),0);for(int i=0;i<ratings.size();i++){if(i>0){if(ratings[i]>ratings[i-1]){candies[i] = candies[i-1]+1;}else{candies[i] = 1;}}else{candies[i] = 1;}}int sum = candies[candies.size()-1];for(int j = ratings.size()-1; j > 0; j--){if(ratings[j-1]>ratings[j]){candies[j-1] = max(candies[j]+1,candies[j-1]);}sum+=candies[j-1];}return sum;}
};
