贪心算法：
贪心无套路，局部最优推全局最优。
455.分发饼干
思路：
尽量大饼干给大需求
先排序，两个数组都从小到大顺序。用num记录多少个孩子吃到了饼干。如果没有孩子或没有饼干，直接返回。int i,j分别为两个数组size-1。进入循环，循环条件是还有孩子和饼干，如果孩子的需求小于等于饼干，则计数加一，孩子和饼干减一，否则孩子减一。最后返回计数num。
看视频后：
这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。
无论有没有吃到，小孩子都会减一。因此用小孩的数组下标作为循环条件，用饼干和小孩的匹配做判断条件。
for(int i=g.size()-1;i>=0;i--)
{
if(index>=0 && s[index]>=g[i])
{
result++;
index--;
}
}
也可以小饼干喂小胃口，则循环顺序变化。
376. 摆动序列
思路：
建立数组minor, int i=1。在i<nums.size()的循环内，分成三种情况：如果相差大于0，则放入差值进minor并进行循环寻找下一个和i-1相差小于等于0的下标；如果相差小于0则放进minor并进行循环找下一个和i-1相差大于等于0的下标；其他情况（等于0）则i++。最后返回minor.size()+1;
看视频后：
局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。
整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。
只需要统计数组的峰值数量就可以了,因此不需要建立数组。
在计算是否有峰值的时候，大家知道遍历的下标 i ，计算 prediff（nums[i] - nums[i-1]） 和 curdiff（nums[i+1] - nums[i]），如果prediff < 0 && curdiff > 0或者prediff > 0 && curdiff < 0此时就有波动就需要统计。
有三种情况：
情况一：上下坡中有平坡
情况二：数组首尾两端
情况三：单调坡中有平坡
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if (nums.size() <= 1) return nums.size();
int curDiff = 0; // 当前一对差值
int preDiff = 0; // 前一对差值
int result = 1; // 记录峰值个数，序列默认序列最右边有一个峰值
for (int i = 0; i < nums.size() - 1; i++) {
curDiff = nums[i + 1] - nums[i];
// 出现峰值
if ((preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)) {
result++;
preDiff = curDiff; // 注意这里，只在摆动变化的时候更新prediff
}
}
return result;
}
};
53. 最大子序和
思路：
1. 两个for循环进行遍历，但是超时了
看视频后：
本题贪心贪在sum如果小于0则会使新的数减小，因此如果sum<0的时候就重新从0开始计数。用result每次比较记录较大值。
int maxSubArray(vector<int>& nums) {
int result=INT_MIN;
int count=0;
for(int i=0;i<nums.size();i++){
count+=nums[i];
if(count>result)
result=count;
if(count<=0)
count=0;
}
return result;
}
