贪心算法理论基础参考：贪心算法基础|代码随想录
不过这个贪心算法没有什么理论基础可言，主要是局部最优推出全局最优，而且没有什么固定的套路或者规律。所以看不看都差不多。
455. 分发饼干
思路：这题比较好想，不然就让大饼干尽量满足胃口大的，这样不会浪费大饼干，不然就让小饼干尽可能满足胃口小的，总而言之都是减少浪费，局部最优之后发现举不出明显的反例，于是可以试试用于全局最优，就AC了。
我的代码：
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(),g.end());
sort(s.begin(),s.end());
int index=s.size()-1;
int result=0;
for(int i=g.size()-1;i>=0;i–) {
if(index>=0&&s[index]>=g[i]) {
index–;
result++;
}
}
return result;
}
};
376. 摆动序列
思路：这道题其实挺难的，要考虑好几种情况：上下坡中有平坡、数组首尾两端、单调坡中有平坡。我们的思路就是删除单一坡度上的节点，让整个序列有最多的局部峰值，从而达到最长摆动序列。其实就我的感觉就是找到这个序列的所有峰值就对了，跟求山峰数量一样。用prediff和curdiff来进行判断，有由于有平坡的情况，所以prediff可以取等于0的情况，即
if((prediff<=0&&curdiff>0)||(prediff>=0&&curdiff<0))
都满足情况。还有注意更新prediff的时候要在摆动状态改变的时候再更新，不用一直更新。
我的代码：
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++) {
int curdiff=nums[i+1]-nums[i];
if((prediff<=0&&curdiff>0)||(prediff>=0&&curdiff<0)) {
result++;
prediff=curdiff;
}
}
return result;
}
};
53. 最大子数组和
思路：这题其实可以暴力解出，如果要用贪心的话就是稍微简化一点，用一个count来统计目前的所有数字的和，如果大于目前最大的结果就更新result,小于0的话就重新更新count。因为小于0的count肯定是拖累整个和的。
我的代码：
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(count>result) result=count;
if(count<=0) count=0;
}
return result;
}
};
今日总结
今天开始学习贪心算法，之前一直以为贪心算法是什么很高深的算法，结果真的学起来”贪心“二字原来是这个意思，不过看到介绍也知道后面的题目会越来越难，感觉这个部分更多是考验你的假设验证能力还有一些创新能力，能不能找到局部最优的情况很关键。
