代码随想录算法训练营第三十四天|1005.K次取反后最大化的数组

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

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

局部最优可以推出全局最优

第一步：将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小

第二步：从前向后遍历，遇到负数将其变为正数，同时K--

第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完

第四步：求和

intlargestSumAfterKNegations(vector<int>&A,intK){sort(A.begin(),A.end(),cmp);// 第一步for(inti=0;i<A.size();i++){// 第二步if(A[i]<0&&K>0){A[i]*=-1;K--;}}if(K%2==1)A[A.size()-1]*=-1;// 第三步intresult=0;for(inta:A)result+=a;// 第四步returnresult;}

这道题比较简单，细节需要注意。

134. 加油站

可以暴力求解，遍历每一个加油站为起点的情况，模拟一圈

for循环适合模拟从头到尾的遍历，而while循环适合模拟环形遍历

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

intcanCompleteCircuit(vector<int>&gas,vector<int>&cost){intcurSum=0;inttotalSum=0;intstart=0;for(inti=0;i<gas.size();i++){curSum+=gas[i]-cost[i];totalSum+=gas[i]-cost[i];if(curSum<0){// 当前累加rest[i]和 curSum一旦小于0start=i+1;// 起始位置更新为i+1curSum=0;// curSum从0开始}}if(totalSum<0)return-1;// 说明怎么走都不可能跑一圈了returnstart;}

135. 分发糖果

采用两次贪心的策略：

一次是从左到右遍历，只比较右边孩子评分比左边大的情况。

一次是从右到左遍历，只比较左边孩子评分比右边大的情况。

局部最优推出了全局最优，即：相邻的孩子中，评分高的孩子获得更多的糖果

intcandy(vector<int>&ratings){vector<int>candyVec(ratings.size(),1);// 从前向后for(inti=1;i<ratings.size();i++){if(ratings[i]>ratings[i-1])candyVec[i]=candyVec[i-1]+1;}// 从后向前for(inti=ratings.size()-2;i>=0;i--){if(ratings[i]>ratings[i+1]){candyVec[i]=max(candyVec[i],candyVec[i+1]+1);}}// 统计结果intresult=0;for(inti=0;i<candyVec.size();i++)result+=candyVec[i];returnresult;}

局部最优：取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，保证第i个小孩的糖果数量既大于左边的也大于右边的

这个细节需要注意！