贪心算法
455. 分发饼干
题意：假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
示例：
思路：这个给出两种思路，但是对数组的处理还是不变，就是为了避免分配浪费，需要从大饼干和大胃口开始做匹配，分配时有两种思路：1.饼干数量不变：这里是指我们使用一个数组存储饼干的使用情况，此时只要判断饼干未被使用且满足孩子胃口，就说明分配成功，总数+1；2.对饼干的数量做出改变：这个好处就是省去了一块空间用于标记未使用的饼干，将当前最大的饼干进行合理分配后，饼干就减少了一个，边界进行--操作，满足总数+1
C++代码：
int findContentChildren(vector<int>& g, vector<int>& s) {
int count=0;
sort(g.begin(),g.end());//我们要从大的饼干开始分配，这样才不会出现浪费的情况
sort(s.begin(),s.end());
vector<int> tmp(g.size(),0);//这里记录被用过的饼干
for(int i=s.size()-1;i>=0;i--)
{
for(int j=g.size()-1;j>=0;j--)
{
if(tmp[j]==0&&s[i]>=g[j])//饼干未被使用且满足孩子的胃口
{
count++;
tmp[j]=1;
break;
}
}
}
return count;
}int findContentChildren(vector<int>& g, vector<int>& s) {
int count=0,end=s.size()-1;
sort(g.begin(),g.end());//让孩子的胃口和饼干都处于从小到大的顺序匹配
sort(s.begin(),s.end());
for(int i=g.size()-1;i>=0;i--)
{
if(end>=0&&s[end]>=g[i])//改变了饼干的边界
{
count++;
end--;
}
}
return count;
}376. 摆动序列
题意：如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。
示例：
思路：本题我们使用两个变量来表示摇摆序列，递增up和递减down，当增加时，up就等于down+1；当递减时，down就等于up+1，这样很好的排除了一直增加和减少的情况，且返回时，返回的是up和down的最大值，也不需要考虑到底是递增先还是递减先
C++代码：
int wiggleMaxLength(vector<int>& nums) {
if(nums.size()<2)
{
return nums.size();
}
int up=1,down=1;
for(int i=1;i<nums.size();i++)//本题利用循环递增的结构，必须递增再递减才能起到摇摆的效果，如果一直递增或递减，也只会增加一次
{
if(nums[i]>nums[i-1])
{
down=up+1;
}
else if(nums[i]<nums[i-1])
{
up=down+1;
}
}
return max(up,down);
}53. 最大子数组和
题意：给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。
示例：
思路：本题我们采用动态规划的思想，创建一个数组dp，然后初始化第一个元素，从第二个元素开始遍历。保存当前元素和当前元素+前面元素的最大和的最大值，当所有元素遍历完，此时dp内就有一个最大子数组和，我们只需要排序dp，并输出最后一个元素即可
还有一种是贪心算法的思想，我们只从正数开始算起，每次让count+当前元素，当count大于结果时，赋值；然后再对count进行判断，如果小于0，则大概率不是我们要的累加树，此时count重置为0，这样循环遍历完就可以得到我们想要的结果
C++代码：
int maxSubArray(vector<int>& nums) {
vector<int> dp(nums.size());
dp[0] = nums[0];
for (int i = 1; i<nums.size(); i++)
{
dp[i] = max(nums[i], nums[i] + dp[i - 1]);
}
sort(dp.begin(), dp.end());
return dp[nums.size() - 1];
}int maxSubArray(vector<int>& nums) {
int result=INT_MIN,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;
}