贪心算法理论基础

选取每一阶段的局部最优，堆叠成全局最优。遇到求最优解问题时，可以先手动模拟一下，将问题分解，举例分析小问题的局部最优是否能达到全部最优，能的话就可以试一下贪心算法。贪心算法的题没有固定的套路和判别方法，基本就是靠常识和手动模拟的方式。
其实算法书中有数学推导，但在面试刷题中用不着。

分发饼干

用大饼干满足胃口大的小孩，小饼干满足胃口小的小孩，尽量不造成饼干的浪费。
对每一个小孩找合适的饼干是可以的，但这既需要遍历小孩也需要遍历饼干。我们可以对小孩的胃口从大到小进行 for 循环，用另一个指针指向最大的饼干，每当匹配上才移动指针，指向次大的饼干。
也可以对饼干从小到大进行 for 循环，用另一个指针指向胃口最小的小孩，满足当前小孩就向后移动指针，指向胃口第二小的小孩。

class Solution{
public:int findContentChildren(vector<int>& g, vector<int>& s){sort(s.begin(), s.end());sort(g.begin(), g.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;}
};

另一种写法

class Solution{
public:int findContentChildren(vector<int>& g, vector<int>& s){sort(s.begin(), s.end());sort(g.begin(), g.end());int result = 0;int index = 0;  // 指向胃口最小的小孩for(int i = 0; i < s.size(); i++){if(index < g.size() && s[i] >= g[index]){  // 如果当前的最小饼干满足了小孩，就去找下一个小孩index++;result++;}}return result;}
};

摆动序列

贪心解法

要从原数组中选择出一个大一个小的序列，只需要删除单调坡上的元素。局部最优就是删除单调坡上除了两个端点以外的中间点，就可以得到两个峰值；全局最优就是峰值点最多的序列，组成最长的摆动序列。贪心体现在我们在遍历时尽量让摆动元素选在局部峰值位置。
那就设计到如何判断一个点是否是局部峰值点，主要是平坡情况带来的干扰。分为以下三种情况：

1. 上下坡中间是平坡
2. 数组首尾有平坡
3. 单调坡中间有平坡

class Solution{
public:int wiggleMaxLength(vector<int>& nums){if(nums.size() == 1)  return 1;int preDiff = 0;  // 上两个元素之间的差初始化为0int curDiff = 0;int result = 1;  // 数组最后一个元素是一个峰值for(int i = 0; i < nums.size() - 1; i++){curDiff = nums[i + 1] - nums[i];  // 求下一个元素与当前元素的差// 将等于0丢给preDiff，这样可以覆盖平坡中的情况1和情况2，总是取平坡的最后一个元素作为峰值if((preDiff >= 0 && curDiff < 0) || (preDiff <= 0 && curDiff > 0)){// 当前元素满足局部峰值条件result++;preDiff = curDiff;  // 因为我们只是判断差值的符号，不需要准确的记录差值，所以只在峰值更新时更新差值，以覆盖平坡中的情况3，不然会把单调坡中的平坡元素记录下来}}return result;}
};

动态规划思路

如何选定一个元素加入摆动序列，它要么被拿来当山峰，要么当做山谷。dp[i][0]表示以元素 i 结尾的摆动序列的最长长度，其中元素i 被当做山峰；dp[i][1]表示以元素 i 结尾的摆动序列的最长长度，其中元素i 被当做山谷。
那么状态转移方程为：
dp[i][0] = max(dp[i][0], dp[j][1] + 1), 0 < j < i && nums[j] < nums[i]，将元素 i 接在以 j 为山谷的元素后面。反之亦然。

class Solution{
public:int wiggleMaxLength(vector<int>& nums){int dp[1000][2];memset(dp, 0, sizeof dp);dp[0][0] = dp[0][1] = 1;  // 以当前元素结尾的摆动序列，当前序列做山峰for(int i = 1; i < nums.size(); i++){dp[i][0] = dp[i][1] = 1;for(int j = 0; j < i; j++){if(nums[i] > nums[j]){dp[i][0] = max(dp[i][0], dp[j][1] + 1);}if(nums[i] < nums[j]){dp[i][1] = max(dp[i][1], dp[j][0] + 1); }}}return max(dp[nums.size() - 1][0], dp[nums.size() - 1][1]);}
};

最大子序和

贪心思路

贪心并不好想，像是[-2,1]这样的数组，我们肯定倾向于选择1。如果当前子数组的和已经为负数，那么这部分和对后续序列只能带来负向的影响。所以贪心的策略就是如果局部序列加和为负，就抛弃该序列，从头开始计算总和，这样会得到很多序列的局部最优，求各个序列的局部最优的最大值，就可以获得全局最优。

class Solution{
public:int maxSubArray(vector<int>& nums){int count = 0;  // 计算局部序列和int result = INT_MIN;  // 更新目前出现的和的最大值for(int i = 0; i < nums.size(); i++){count += nums[i];if(count > result){result = count;  // 在求局部最优的过程就更新全局最优的值}if(count < 0){count = 0;  // 当前的序列和已经小于0，重新记录总和}}return result;}
};

动态规划思路

这个比较好想，当前序列的和一定是与上一个序列是相关的。设dp[i]表示以元素 i 为结尾的序列的最大和，可以得到转移方程dp[i] = max(dp[i - 1] + nums[i], nums[i])，要么重新记和，要么加上之前的序列，取最大值。

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