文章参考来源代码随想录
贪心算法：局部最优到全局最优
455.分发饼干
这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩
可以尝试使用贪心策略，先将饼干数组和小孩数组排序
然后从后向前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(),g.end());
sort(s.begin(),s.end());
int result=0;
int index=s.size()-1;
for(int i=g.size()-1;i>=0;i--){
if(index>=0&&s[index]>=g[i]){
result++;
index--;
}
}
return result;
}
};用了一个 index 来控制饼干数组的遍历（以此标记取过的饼干），遍历饼干并没有再起一个 for 循环，而是采用自减的方式，这也是常用的技巧。
376. 摆动序列
局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。其实这里不用删除，只需要记录个数就行了。
整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。
前峰值，当前峰值；
峰值时计数器+1。
情况一：上下坡中有平坡
这里规定删除左边的节点，因此判断峰值条件就变为(prediff>=0&&curdiff<0)||(prediff<=0&&curdiff>0)
那么 当 prediff = 0 && curdiff < 0 也要记录一个峰值，因为他是把之前相同的元素都删掉留下的峰值。
情况二：数组首尾两端
题目中说了，如果只有两个不同的元素，那摆动序列也是 2。
因为我们在计算 prediff（nums[i] - nums[i-1]） 和 curdiff（nums[i+1] - nums[i]）的时候，至少需要三个数字才能计算，而数组只有两个数字。
这里我们可以写死，就是 如果只有两个元素，且元素不同，那么结果为 2。
之前我们在 讨论 情况一：相同数字连续 的时候， prediff = 0 ，curdiff < 0 或者 >0 也记为波谷。
那么为了规则统一，针对序列[2,5]，可以假设为[2,2,5]，这样它就有坡度了即 preDiff = 0，如图：
针对以上情形，result 初始为 1（默认最右面有一个峰值），此时 curDiff > 0 && preDiff <= 0，那么 result++（计算了左面的峰值），最后得到的 result 就是 2（峰值个数为 2 即摆动序列长度为 2）
情况三：单调坡度有平坡
我们只需要在 这个坡度 摆动变化的时候，更新 prediff 就行，这样 prediff 在 单调区间有平坡的时候 就不会发生变化，造成我们的误判。就是把prediff=curdiff;提到if中。
53. 最大子序和
局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。
全局最优：选取最大“连续和”。
count记为连续和，结果为result。
当结果小于连续和时，后者赋给前者；（本质是不断确定区间结束位置）
当连续和为负时，重置连续和；（本质是不断确定区间开始位置）
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int result=INT_MIN;
int count=0;
for(int i=0;i<nums.size();i++){
count+=nums[i];
if(result<count)result=count;
if(count<=0)count=0;
}
return result;
}
};