代码随想录day30【贪心算法】分发饼干 摆动序列 最大子数组和

分发饼干

力扣题目链接
思路：大饼干优先满足胃口大的孩子。

var findContentChildren = function(g, s) {
    g.sort((a,b)=>a-b)
    s.sort((a,b)=>a-b)
    let res=0
    let index=s.length-1
    for(let i=g.length-1;i>=0;i--){
        if(index>=0 && g[i]<=s[index]){
            res++
            index--
        }
    }
    return res
};

摆动序列

leecode题目
思路：
局部最优：单调坡的元素都删除掉
全局最优：得到最长摆动序列

image.png

分析：
三种情况：

1. 上下坡有平坡
2. 只有首尾元素
3. 单调坡有平坡

var wiggleMaxLength = function(nums) {
    let res=1 //初始为1:默认最后一个元素有摆动
    let preDiff=0
    let curDiff=0

    for(let i=0;i<nums.length-1;i++){
        curDiff= nums[i+1]-nums[i]
        if(preDiff <=0 && curDiff>0){
            res++
            preDiff= curDiff
        }else if(preDiff >=0 && curDiff <0){
            res++
            preDiff= curDiff
        }
    }
    return res
};

最大子数组

力扣题目链接
思路：
局部最优：当连续和为负数时，选择下一个数作为新的起点，重新开始计算连续和
全局最优：找到最大连续子数组

var maxSubArray = function(nums) {
  let count=0
  let res=nums[0]
  for(let i=0;i<nums.length;i++){
      count +=nums[i]
      res=Math.max(res,count)

      if(count<0){
          count = 0 
      }

  }
  return res
};