算法训练营day27(补)，贪心算法1
import "sort"
//455. 分发饼干
func findContentChildren(g []int, s []int) int {
sort.Ints(g)
sort.Ints(s)
// g代表胃口数组， s代表饼干数组
count := 0 // 统计数量
//饼干下标
index := len(s) - 1
// 胃口循环
for i := len(g) - 1; i >= 0; i-- {
if index >= 0 && s[index] >= g[i] {
count++
index--
}
}
return count
}
/*
376. 摆动序列
本题要考虑三种情况：
情况一：上下坡中有平坡
情况二：数组首尾两端
情况三：单调坡中有平坡
*/
func wiggleMaxLength(nums []int) int {
prev := 0 //前指针
cur := 0 //当前指针
result := 1 //记录峰值个数
for i := 0; i < len(nums)-1; i++ {
cur = nums[i+1] - nums[i]
// 出现峰值
if (prev >= 0 && cur < 0) || (prev <= 0 && cur > 0) {
result++
prev = cur
}
}
return result
}
//53. 最大子数组和
func maxSubArray(nums []int) int {
maxSum := nums[0]
count := 0
for i := 0; i < len(nums); i++ {
count += nums[i]
if count >= maxSum { //取子序列和最大值
maxSum = count
}
if count <= 0 { //当子序列和小于0重置起始位
count = 0
}
}
return maxSum
}