1005. K 次取反后最大化的数组和
思路：
要实现最大值，首先是将数组中的负数取反转换为正数，绝对值大的负数优先。如果所有的负数都已经转为正数，但是k不为0，则将最小的正数进行取反，直到k为0。
代码：
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(k>0 && nums[i]<0)
{
nums[i]=-nums[i];
k--;
}
}
if(k%2==1)nums[nums.size()-1]*=-1;
int res=0;
for(int i=0;i<nums.size();i++)
{
res+=nums[i];
}
return res;
}
};
134. 加油站
思路：
这道题与第122题有相似之处，如果在第i处的净值小于0，则表示i之前的站点出发都不行，应该从i+1处重新计算。
代码：
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int cursum=0;
int totalsum=0;
int index=0;
for(int i=0;i<gas.size();i++)
{
cursum+=gas[i]-cost[i];
totalsum+=gas[i]-cost[i];
if(cursum<0)
{
index=i+1;
cursum=0;
}
}
if(totalsum<0) return -1;
return index;
}
};
135. 分发糖果
思路：
这道题的难点在于对于数组中间的数字，既要跟左边比较又要跟右边比较，此类问题可以分两部求解，先从头遍历，比较左边的情况，再从尾部倒序遍历，比较右边，最后求两者的交集（最大值）。
代码：
class Solution {
public:
int candy(vector<int>& ratings) {
vector<int> res(ratings.size(),1);
for(int i=1;i<ratings.size();i++)
{
if(ratings[i]>ratings[i-1])
{
res[i]=res[i-1]+1;
}
}
for(int i=ratings.size()-2;i>=0;i--)
{
if(ratings[i]>ratings[i+1])
res[i]=max(res[i],res[i+1]+1);
}
int sum=0;
for(int i=0;i<res.size();i++)
{
sum+=res[i];
}
return sum;
}
};
