算法训练营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

}