算法训练day31｜贪心算法part1

理论基础：

贪心算法没有模版

通过找到局部最优解来获得全剧最优解

455.分发饼干

大饼干给大胃口

先遍历胃口再遍历饼干

小饼干给小需求

先遍历饼干，再遍历胃口

376. 摆动序列

局部最优：同一趋势下，只用管最大值和最小值，

全剧最优：整个序列有最多的局部峰值，从而达到最长摆动序列

1. 情况一：上下坡中有平坡
2. 情况二：数组首尾两端
3. 情况三：单调坡中有平坡

为了应对情况1，我们只计入平->摆的部分?所以我们记录峰值的条件应该是：?(preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)

为了应对情况2，

prevdiff初始值为0，这样会记录右边的端点（至少有两个值的时候）

result 初始化为1，默认记录了左边的端点

nums数量小于2的时候直接返回nums.length

为了应对情况3，我们只在有峰值记录的时候才记录prevdiff，prevdiff更像是记录之前的整体趋势的

动态规划

For every position in the array, there are only three possible statuses for it.

• up position, it means nums[i] > nums[i-1]
• down position, it means nums[i] < nums[i-1]
• equals to position, nums[i] == nums[i-1]

So we can use two arrays up[] and down[] to record?the max wiggle sequence length so far?at index?i.
If nums[i] > nums[i-1], that means it wiggles up. the element before it must be a down position. so up[i] = down[i-1] + 1; down[i] keeps the same with before.
If nums[i] < nums[i-1], that means it wiggles down. the element before it must be a up position. so down[i] = up[i-1] + 1; up[i] keeps the same with before.
If nums[i] == nums[i-1], that means it will not change anything becasue it didn't wiggle at all. so both down[i] and up[i] keep the same.

In fact, we can reduce the space complexity to O(1), but current way is more easy to understanding.

public class Solution {
    public int wiggleMaxLength(int[] nums) {
        
        if( nums.length == 0 ) return 0;
        
        int[] up = new int[nums.length];
        int[] down = new int[nums.length];
        
        up[0] = 1;
        down[0] = 1;
        
        for(int i = 1 ; i < nums.length; i++){
            if( nums[i] > nums[i-1] ){
                up[i] = down[i-1]+1;
                down[i] = down[i-1];
            }else if( nums[i] < nums[i-1]){
                down[i] = up[i-1]+1;
                up[i] = up[i-1];
            }else{
                down[i] = down[i-1];
                up[i] = up[i-1];
            }
        }
        
        return Math.max(down[nums.length-1],up[nums.length-1]);
    }
}

53. 最大子序和

如果前面的连续和为负数就立刻放弃

用这次的nums[i]作为连续和第一个数

一直记录连续和的最大值