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

把数组先排序，排序好后根据k和数组长度中最小的那个进行遍历，目的是如果有负数的就把他们从小到大依次取正，然后按照还剩下的k的数量来判断，如果是偶数则按照当前数组输出，如果是奇数则需要把当前数组的最小值取反再求和。

class Solution:def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:nums.sort()count = 0for i in range(min(k, len(nums))):if nums[i]<0:count += 1nums[i] = -nums[i]elif nums[i]>=0:breakremain = k - countprint(remain, nums)if remain % 2 == 0:return sum(nums)else:nums.sort()return sum(nums) - 2 * nums[0]

假设从0出发，保证每一次加完油跑到下一个站点时油量大于等于0，如果油量小于零了就把启示站移到下一个加油站，如果总的gas和小于cost的和那怎么都是不能跑完全程，返回-1。

class Solution:def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:total_gas = 0cur_gas = 0start = 0for i in range(len(gas)):cur_gas += gas[i] - cost[i]total_gas += gas[i] - cost[i]if cur_gas < 0:start = i + 1cur_gas = 0if total_gas < 0:return -1else:return start

分两次局部最优，第一次是从左往右，如果右边的分大于左边的， 就让右边的糖果比左边的多1个。第二次是从右往左，如果左边的分大于右边的，如果左边的糖果本来就大于右边的则不变，否则变成右边的+1。

class Solution:def candy(self, ratings: List[int]) -> int:n = len(ratings)candys = [1 for _ in ratings]for i in range(1,n):if ratings[i] > ratings[i-1]:candys[i] = candys[i-1] + 1for i in range(n-1, 0,-1):if ratings[i-1] > ratings[i]:candys[i-1] = max(candys[i] + 1, candys[i-1])return sum(candys)