455.分发饼干

先给孩子和饼干排序，每次选取一个最大的饼干给一个最大胃口的孩子，直到饼干分完或者遍历完孩子

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 res = 0;
        for (int i = g.size() - 1; i >= 0; i--) {
            if (index >= 0 && s[index] >= g[i]) {
                index--;
                res++;
            }
        }
        return res;
    }
};

或者换一种想法，从小到大遍历饼干，每次分配一个饼干给小朋友，能给index就++

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int index = 0;
        for (int i = 0; i < s.size(); i++) {
            if (index < g.size() && s[i] >= g[index]) {
                index++;
            }
        }
        return index;
    }
};

376.摆动序列

如果只有一个元素，则答案为1
如果有两个元素，则如果两个元素不相同，答案为2，否则为1
这是需要注意的地方

本题需要绘制一个图，能看出来峰值的关系

只需要把那些非峰值上的点删除，就是最长的摆动序列
因为对于非峰值的点，其都是无关紧要的
当坡度发生变化时，只需要找到该坡度里的极点即可

局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。
整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列

本题要考虑三种情况：

情况一：上下坡中有平坡

可以统一规则，删除前面的3个2，留下最后一个，序列变成[1,2,1]，答案为3

当 i 指向第一个 2 的时候，prediff > 0 && curdiff = 0 ，当 i 指向最后一个 2 的时候 prediff = 0 && curdiff < 0
当 prediff = 0 && curdiff < 0 也要记录一个峰值，因为他是把之前相同的元素都删掉留下的峰值。
所以我们记录峰值的条件应该是： (preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)
那么如果选择保留第一个2，删除其余2的时候，额外的判断条件应该是prediff!=0 && curdiff=0

情况二：数组首尾两端
对于左右端点的判断情况
如果只有两个不同的元素，那摆动序列也是 2
例如序列[2,5]，如果靠统计差值来计算峰值个数就需要考虑数组最左面和最右面的特殊情况。
左端点是没有prediff的，右端点没有curdiff,如果不需要写if特判的话，那么我们需要假设左端点前面有一个虚拟端点，其值和左端点是一样的，则左端点prediff=0

而对于右端点，我们直接假设其已经是一个峰值了（其必定为一个峰值，因为它是最后一个元素，可以画图想一下原理，要么就是极值，要么就是摆动的第一个元素），所以我们答案初始就为1
针对以上情形，result 初始为 1（默认最右面有一个峰值），对于左端点，此时 curDiff > 0 && preDiff <= 0，那么 result++（计算了左面的峰值），最后得到的 result 就是 2（峰值个数为 2 即摆动序列长度为 2）

情况三：单调坡中有平坡
我们忽略了一种情况，即 如果在一个单调坡度上有平坡

如果按照之前的条件
(preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)
那么在最后一个2的时候，result就会+1，这明显是不对的，因为答案应该为2->序列是[1,4]
之所以会出问题是因为prediff实时更新
我们应该在坡度变化的时候再用curdiff更新prediff，这样它记录了之前的坡度方向(大于0和小于0），这样到1的时候prediff被更新为1，表示是一个上坡，然后坡度没变化的时候prediff一直是1，到了最后一个2的时候prediff>0,curdiff>0,所以长度不会增加

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.size() <= 1)
            return nums.size();
        int curdif = 0;
        int predif = 0;
        int res = 1;
        for (int i = 0; i < nums.size() - 1; i++) {
            curdif = nums[i + 1] - nums[i];
            if ((predif <= 0 && curdif > 0) || (predif >= 0 && curdif < 0)) {
                res++;
                // 只有坡度变化才记录
                predif = curdif;
            }
        }
        return res;
    }
};

53.最大子数组和

贪心
局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。

全局最优：选取最大“连续和”
局部最优的情况下，并记录最大的“连续和”，可以推出全局最优。

从代码角度上来讲：遍历 nums，从头开始用 sum 累积，如果 sum一旦加上 nums[i]变为负数，那么就应该从 nums[i+1]开始从 0 累积 sum 了，因为已经变为负数的 count，只会拖累总和。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.size() == 1)
            return nums[0];
        int sum = 0;
        int res = -INT_MAX;
        for (int i = 0; i < nums.size(); i++) {
            if (sum <= 0)
                sum = 0;
            sum += nums[i];
            res = max(res, sum);
        }
        return res;
    }
};

用前缀和的做法也是可以的，用两个变量
maxsum和minprefixsum来分别记录遍历到的最大子数组和以及最小前缀和
首先计算前缀和数组，sum[0] = 0
maxsum初始化为最小的int，minprefixsum初始化为0.
从前往后依次遍历各个前缀和，记录最大的前缀和之差，将其保存在maxsum，因为前缀和之差就是区间和
同时记录最小的前缀和，因为一个后面的前缀和 sum[i]减去前面最小的前缀和minprefixsum,得到的一定是以当前数nums[i-1]为右端点的最大的区间和

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.size() == 1)
            return nums[0];
        int n = nums.size();
        vector<int> sum(n + 1, 0);
        for (int i = 0; i < nums.size(); i++) {
            sum[i + 1] = sum[i] + nums[i];
        }
        int maxsum = INT_MIN;
        int minprefixsum = sum[0];
        for (int i = 1; i <= n; i++) {
            maxsum = max(maxsum, sum[i] - minprefixsum);
            minprefixsum = min(minprefixsum, sum[i]);
        }

        return maxsum;
    }
};