代码随想录算法训练营 | 贪心算法：455.分发饼干，376. 摆动序列，53. 最大子序和

455.分发饼干
题目链接：455.分发饼干
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰分发饼干
日期：2024-10-02

想法：大饼干喂大孩子
Java代码如下：

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int count = 0;
        int index = s.length - 1;
        for(int i = g.length - 1; i >= 0; i--) {
            if(index >= 0 && g[i] <= s[index]) {
                count++;
                index--;
            }
        }
        return count;
    }
}

376. 摆动序列
题目链接：376. 摆动序列
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰摆动序列
日期：2024-10-02

想法：考虑平坡， 平坡分两种，一个是上下中间有平坡，一个是单调有平坡
Java代码如下：

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length <= 1) {
            return nums.length;
        }
        int curDiff = 0;
        int preDiff = 0;
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            curDiff = nums[i] - nums[i - 1];
            if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)) {
                count++;
                preDiff = curDiff;
            }
        }
        return count;
    }
}

53. 最大子序和
题目链接：53. 最大子序和
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰最大子序和
日期：2024-10-02

想法：局部最优：和为负则舍弃当前区间，从下一个重新开始算。
Java代码如下：

class Solution {
    public int maxSubArray(int[] nums) {
        if (nums.length == 1){
            return nums[0];
        }
        int sum = Integer.MIN_VALUE;
        int count = 0;
        for (int i = 0; i < nums.length; i++){
            count += nums[i];
            sum = Math.max(sum, count);
            if (count <= 0){
                count = 0;
            }
        }
       return sum;
    }
}