一. 学习文章及资料

二. 学习内容

1. 理论基础

算法>贪心算法无规律！

一般如想到局部最优，好像能推出全局最优，并且无明显反例，那就试一试！

2. 分发饼干

(1) 解题思路：

使用贪心策略，先将饼干数组和小孩数组排序。然后从后向前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量。

                           

(2) 解题步骤：

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

3. 摆动序列

(1) 解题思路：
局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。
全局最优：整个序列有最多的局部峰值，从而达到最长摆动序列。
实际操作上，只需统计数组的峰值数量就可以了（相当于是删除单一坡度上的节点，然后统计长度）

• 情况一：上下坡中有平坡

• 情况二：数组首尾两端

如只有两个不同数字，那默认最右边有峰值。如 [2,5], result 初始为 1（默认最右面有一个峰值），i为0，指向2，此时 curDiff > 0 && preDiff <= 0，那么 result++（计算了左面的峰值），最后得到的 result 就是 2（峰值个数为 2 即摆动序列长度为 2）

• 情况三：单调坡中有平坡

在这个坡度摆动变化的时候，更新 preDiff 就行，这样 preDiff 在 单调区间有平坡的时候就不会发生变化，造成我们的误判。

class Solution {public int wiggleMaxLength(int[] nums) {if(nums.length<=1) return nums.length;int perDiff=0;//前一对差值int curDiff=0;//现一对差值int result=1; //记录峰值个数，序列默认序列最右边有一个峰值for(int i=0;i<nums.length-1;i++){//只遍历到倒数第二个，因为默认序列最右边有一个峰值curDiff=nums[i+1]-nums[i];//出现峰值if(perDiff>=0&&curDiff<0||perDiff<=0&&curDiff>0){result++;perDiff=curDiff;//注意这里，只在摆动变化的时候更新prediff}}return result;}
}

4. 最大子序和

(1) 解题思路：

局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。
全局最优：选取最大“连续和”
局部最优的情况下，并记录最大的“连续和”，可以推出全局最优

                       

class Solution {public int maxSubArray(int[] nums) {int result=Integer.MIN_VALUE;int sum=0;for(int i=0;i<nums.length;i++){sum+=nums[i];if(sum>result) result=sum;//取区间累计的最大值（相当于不断确定最大子序终止位置）if(sum<0) sum=0; //相当于重置最大子序起始位置，因为遇到负数一定是拉低总和}return result;}
}