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

首先将数组按绝对值从大到小排列，然后对于数组中的负数取相反数（如果k比负数多，就把最后的（绝对值最小的）取相反数）

贪心：局部最优：让绝对值大的负数变为正数，当前数值达到最大，整体最优：整个数组和达到最大。

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. 加油站

循环序列查找的方法可以采用取模的方式：

index=i%cost.size();

暴力求解（会导致时间限制）：

class Solution
{
public:int canCompleteCircuit(vector<int> &gas, vector<int> &cost){for(int i = 0; i < gas.size(); i++){int rest = gas[i] - cost[i];int index = (i + 1) % gas.size();while(rest>0&&index!=i){rest += gas[index] - cost[index];index = (index + 1) % gas.size();}if(rest>=0&&index==i)return i;}return -1;}
};

贪心算法（局部最优：当前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因为从i之前开始一定不行。全局最优：找到可以跑一圈的起始位置）：

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. 分发糖果

先前思路：先找到最小的，给一个糖，然后遍历他的左右，大的给加个，小的给减一个，然后加起来，写不出来

正经思路：从前向后，找右大于左的情况；从后向前遍历，找左大于右的情况。

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]>ratings[i-1]){candyVec[i] = candyVec[i - 1] + 1;}}for(int i=ratings.size()-2; i>=0;i--){if(ratings[i]>ratings[i+1]){candyVec[i] = max(candyVec[i], candyVec[i+1]+1);}}int result = 0;for(int i=0; i<candyVec.size();i++){result += candyVec[i];}return result;}
};