1005.K次取反后最大化的数组和
我是暴力算出来的，看题解后知道了新的解法。
本题求的是将元素翻转k次后数组最大和，每个元素可重复翻转。
先将数组排序后，绝对值大的负数就在前面，优先翻转他们。因此排序后从前向后遍历数组，做k次改变，因此循环k次。
定义idx指向绝对值最小的元素，当数字都为正数时翻转绝对值最小的元素和的损失最小。
若还没有遍历到正数，则当前负数绝对值一定比后一个元素绝对值大。idx指向当前遍历的负数。
若遍历到最后一个负数，当前元素绝对值若大于正数绝对值，则修改正数的符号。让idx++指向那个正数。
循环k此后即为修改好的数组。
135. 分发糖果?本题为分发糖果，每个孩子最少一个，若当前孩子得分大于左/右孩子，则糖果数也大于左/右孩子。若等于，则没有要求。
本题注意要分两次情况遍历数组，不能同时兼顾左右孩子
i从1开始，先和左孩子i-1比较，从前向后比较。
? ? ? ? 注意：i=0没有左孩子，不用进行比较。
i从len-2,开始，再和右孩子i+1比较，从后向前比较。
? ? ? ? 注意：i=len-1没有右孩子，当len-1大于len-2时，因为已经从左向右遍历过了，因此len-1的糖果值始终为len-2+1.若len-1小于len-2，则len-1糖果值始终为1。因此不用遍历len-1.
//倒数第二个孩子如果小于倒数第一个孩子大于倒数第三个孩子，那么在第一轮循环的时候就会定型。如果倒数第二个孩子大于倒数第一个孩子那么倒数第二个孩子的糖果值就是倒数第一个孩子糖果值加一。因此无论怎样倒数第一个孩子的糖果值都不会变。 134.?加油站我自己写的暴力超时了，哈哈。
本题我没有想到的核心：若gas数组和大于cost数组和，那么一定能走完全程（其实不是很理解）
定义total记录gas和cost数组和之差，若total<0，return -1，不能走完一圈。
那么假设一定能走完一圈，定义cursum为前面的累加和，start作为起始位置。若[0,i]的累加和<0，说明i之前一定不能作为起始位置，继续累加cursum，start从i+1开始。最后返回start即可。
 1.本站遵循行业规范，任何转载的稿件都会明确标注作者和来源；2.本站的原创文章，会注明原创字样,如未注明都非原创，如有侵权请联系删除！；3.作者投稿可能会经我们编辑修改或补充；4.本站不提供任何储存功能只提供收集或者投稿人的网盘链接。 |
