题目：1005.K次取反后最大化的数组和
思路：
思路是：
- 先把负数从小到大变成正数(即绝对值由大到小)
- 如果还需要变化(k>0)，就变化最小的数
在第一步变化的同时顺便记录一个数组和，那么结束之后会有三种情况：
- k == 0；也就是说负数的个数大于等于k，直接返回结果
- k % 2 == 0; 此时全是正整数，如果k是偶数的话，可以相当于没有变化，直接返回结果
- k % 2 != 0; 此时全是正整数，如果k是奇数的话，需要把最小的数变成负数，因为之前res里已经添加了最小，因此需要
- 2 * nums[0]。
代码1：
func largestSumAfterKNegations(nums []int, k int) int {
res := 0
lens := len(nums)
sort.Ints(nums) // 排序
for i := 0; i < lens; i++ { // 一边把负数变正一边求和
if nums[i] >= 0 { // 求和1
res += nums[i]
continue
}
if k > 0 { // 如果k大于0就可以变
nums[i] = -nums[i]
k--
}
res += nums[i] // 求和2
}
sort.Ints(nums) // 变完之后再排序一次
if k % 2 == 1 { // 如果k剩下奇数个，把最小的元素去掉即可(因为之前加了，所以要减去2 * nums[0]
res -= 2 * nums[0]
}
return res
}
代码2：
func largestSumAfterKNegations(nums []int, k int) int {
res := 0
lens := len(nums)
sort.Slice(nums, func(i, j int) bool { // 用这个直接求绝对值的排序(由大到小)
return math.Abs(float64(nums[i])) > math.Abs(float64(nums[j]))
})
for i := 0; i < lens; i++ {
if nums[i] >= 0 {
res += nums[i]
continue
}
if k > 0 { // 这样也会先添加大的负数
nums[i] = -nums[i]
k--
}
res += nums[i]
}
if k % 2 == 1 {
res -= 2 * nums[lens-1] // 最小的元素是nums[lens-1]
}
return res
}
参考：
题目：134. 加油站
思路：
其实这个思路和最大子序列和差不多：如果正向是负向效果(油会更少)，那么在这里开始肯定不行所以没必要遍历这种index，如果是正向效果，那我的tmp之前有数的话岂不是更好？所以直接for一边就可以。
代码：
func canCompleteCircuit(gas []int, cost []int) int {
gas = append(gas, gas...)
cost = append(cost, cost...)
lens := len(gas)
tmp := 0
index := 0 // 记录起始位置
for i := 0; i < lens; i++ {
tmp += gas[i] - cost[i] // 记录当前剩下的油
if tmp < 0 { // 小于0就跑不了
tmp = 0
index = i + 1 // 试试下一个点
continue
}
if i - index == lens / 2 - 1 { // 如果跑完了全程就返回index
return index
}
}
return -1
}
参考：
题目：135. 分发糖果
思路：
本题采用了两次贪心的策略：
一次是从左到右遍历，只比较右边孩子评分比左边大的情况。
一次是从右到左遍历，只比较左边孩子评分比右边大的情况。
这样从局部最优推出了全局最优，即：相邻的孩子中，评分高的孩子获得更多的糖果。
代码：
func candy(ratings []int) int {
/**先确定一边，再确定另外一边
1.先从左到右，当右边的大于左边的就加1
2.再从右到左，当左边的大于右边的就再加1
**/
need := make([]int, len(ratings))
sum := 0
// 初始化(每个人至少一个糖果)
for i := 0; i < len(ratings); i++ {
need[i] = 1
}
// 1.先从左到右，当右边的大于左边的就加1
for i := 0; i < len(ratings) - 1; i++ {
if ratings[i] < ratings[i+1] {
need[i+1] = need[i] + 1
}
}
// 2.再从右到左，当左边的大于右边的就右边加1，但要花费糖果最少，所以需要做下判断
for i := len(ratings)-1; i > 0; i-- {
if ratings[i-1] > ratings[i] {
need[i-1] = findMax(need[i-1], need[i]+1)
}
}
//计算总共糖果
for i := 0; i < len(ratings); i++ {
sum += need[i]
}
return sum
}
func findMax(num1 int, num2 int) int {
if num1 > num2 {
return num1
}
return num2
}