1.贪心算法理论基础

贪心算法一般步骤如下：

• 将问题分解为若干个子问题
• 找出适合的贪心策略
• 求解每一个子问题的最优解
• 将局部最优解堆叠成全局最优解

  2.分发饼干

  解题思路:每个人拿到刚好或尽可能接近能够满足自己的饼干。

  func findContentChildren(g []int, s []int) int {
  	result :=0
  	si := 0
  	sort.Ints(g)
  	sort.Ints(s)
  	for i := 0; i < len(g);  {
  		if si==len(s){
  			break
  		}
  		if g[i]<=s[si]{
  			result++
  			si++
              i++
  		}else{
              si++
          }
  	}
  	return result
  }
  

  3.摆动序列

  解题思路：通过相邻两个数之差进行判断

  func wiggleMaxLength(nums []int) int {
      var prev int
      res := 1
      i := 1
      for i < len(nums) && nums[i] - nums[0] == 0 {
          i++
      }
      if i == len(nums) {
          return res
      }
      res++
      prev = nums[i] - nums[0]
      i++
      for i < len(nums){
          if (nums[i] - nums[i-1]) * prev < 0 {
              prev = nums[i] - nums[i-1]
              res++
          }
          i++
      }
      return res
  }
  

  4.最大子序和

  解题思路：需要考虑整个数组都是负数的情况。

  func maxSubArray(nums []int) int {
      max := nums[0]
      count := 0
      for i := 0; i < len(nums); i++{
          count += nums[i]
          if count > max{
              max = count
          }
          if count < 0 {
              count = 0
          }
      } 
      return max
  }