【算法】贪心

贪心算法没有固定的套路，难点就是图和通过局部最优，推出整体最优。

最好的策略就是举反例，想不到范例，那就可以试一试贪心。

想清楚局部最优和全局最优，感觉局部最优可以推出全局最优，并想不出返例，就可以试试贪心。

分发饼干

https://leetcode-cn.com/problems/assign-cookies/submissions/

这里的局部最优解就是大饼干喂给胃口大的，充分利用饼干尺寸，全局最优就是喂饱尽可能多的小孩。

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

摆动序列

https://leetcode-cn.com/problems/wiggle-subsequence/

局部最优：将一个单调序列中除了两个峰值的其它元素删除掉

全局最优：将序列中的所有单调部分除了局部峰值都删除掉

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 ((curDiff > 0 && preDiff <= 0) || (preDiff >= 0 && curDiff < 0)) {
                result++;
                preDiff = curDiff;
            }
        }
        return result;
    }
};

最大子序和

https://leetcode-cn.com/problems/maximum-subarray/

局部最优：当前连续和为负数时立刻放弃，从下一个元素重新计算连续和

全局最优：选取最大连续和

// 贪心
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = -100000；
        int count = 0;
        for (int i = 0; i < nums.size(); i++) {
            count += nums[i];
            res = max(count, res);
            if (count < 0) count = 0; // 如果前面的子序列和小于0，那么就不要选了
        }
        return res;
    }
};

// 动规
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int dp[100005];
        dp[0] = nums[0];
        int res = dp[0];
        for (int i = 1; i < nums.size(); i++) {
            dp[i] = max(dp[i - 1] + nums[i], nums[i]); // 状态转移
            res = max(dp[i], res);
        }
        return res;
    }
};