这几天做了俩道比较经典的贪心算法的题目，在这里简单得记录一下心得，与诸君共勉。
废话不多说，先抛来俩道经典贪心题吧。
334. 递增的三元子序列
https://leetcode-cn.com/problems/increasing-triplet-subsequence/
给你一个整数数组
nums，判断这个数组中是否存在长度为3的递增子序列。如果存在这样的三元组下标
(i, j, k)且满足i < j < k，使得nums[i] < nums[j] < nums[k]，返回true；否则，返回false。
示例 1：
输入：nums = [1,2,3,4,5]
输出：true
解释：任何 i < j < k 的三元组都满足题意
示例 2：输入：nums = [5,4,3,2,1]
输出：false
解释：不存在满足题意的三元组
示例 3：输入：nums = [2,1,5,0,4,6]
输出：true
解释：三元组 (3, 4, 5) 满足题意，因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6
122. 买卖股票的最佳时机 II
给定一个数组
prices，其中prices[i]是一支给定股票第i天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:输入: prices = [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:输入: prices = [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
先把基于贪心的解题代码附上。
1.递增三元组
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int minf=INT_MAX;
int mins=INT_MAX;
int n=nums.size();
for(int i=0;i<n;i++){
if(nums[i]<=minf)minf=nums[i];
else if(nums[i]<=mins)mins=nums[i];
else return true;
}
return false;
}
};
2.买卖股票的最佳时机（不限制交易次数）
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len=prices.size();
if(len==1)return 0;
int index=0;
int res=0;
while(index<len){
while(index<len-1 && prices[index]>=prices[index+1]){
index++;
}
int minprice=prices[index];
while(index<len-1 && prices[index]<=prices[index+1]){
index++;
}
res+=prices[index++]-minprice;
}
return res;
}
};哈哈，看完代码的第一反应是不是，哇，这代码怎么怎么短？？而其实短小精悍也。
其实这正是贪心算法的体现啊。所以now进入正题吧，当然先打个预防针，正题不会太长，所以屏幕前的你也别指望看下去就能修炼出来贪心算法的精髓啊哈哈（不是劝退啊~）主要是先观其大略，领会一下贪心算法的精髓，日后好相见嘛。
贪心算法，又Greedy Algorithm，顾名思义，就是基于贪心策略的算法，它总是试图根据当前的选择形势选择出当前情况下的最优解，也就是趋向寻找一个局部最优解，如果当前的选择策略能够被严格证明扩展迭代至全局也成立最优解的情况，那么这样的贪心策略便能够求出全局最优解，有不少题目正是基于这样的策略，递推出全局最优解的策略，比如经典单源最短路和最小生成树问题，另外，当然基于贪心策略不起效果的时候，我们这个时候便可以考虑动态规划了，动态规划的思想便是时刻考虑全局条件，本质是内嵌全局枚举的思想，通过避免重复子问题的运算来由局部最优解递推至全局最优解。
而事实上，也有不少动态规划的核心状态转移方程的建立也是通过贪心策略去摸索的，当贪心策略能够被证明推广至全局也成立的话，那不就是一个简单化的动态规划嘛。
贪心算法的基本思路：
从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。
该算法存在问题：
1. 不能保证求得的最后解是最佳的；
2. 不能用来求最大或最小解问题；
3. 只能求满足某些约束条件的可行解的范围。
实现该算法的过程：
从问题的某一初始解出发；
while 能朝给定总目标前进一步 do
求出可行解的一个解元素；
由所有解元素组合成问题的一个可行解。
其实，，，，，以上这么多，就是贪心算法的核心内容了，再往下讲也实在憋不出什么东西了，如果你有点收获或者感悟或者被典型，那真的是我的荣幸了，如果你还是一知半解、满头雾水（或者是半头？哈哈），那就趁着你点进来的这样一个缘分和机会就现在拿上面俩到题目练练吧，强化一下自己的理解。
以第一题递增的三元组为例，考虑每次选择的情况，我们很贪心，我就是不想考虑那些前前后后乱七八糟的限制条件，它不是要我们找递增的三个数，那我就贪心地在数组里面走一遍，看到最小的就拿来（保存下来），看到更新的就换掉，找到次小的再拿来，但要是遇到一个比最小的要大，又比次小的要大，我就贪心地认为存在这样一个三元组了。而这般贪心策略便一致无差得体现在代码上面了，有劳读者在把鼠标滑回去看看呗。
那问题来了，这么贪心的做法能保证得到正确答案吗？比如你肯定会问，如果你存的那个最小值或者次小值原本在前面的，可是后来又在后面被更新了，或者俩个小值恰有一个在后来被更新了，如此种种，这能保证结果真的符合题意吗。
于是便是贪心的最关键的一步，推广证明。
我们如果能证明这种策略在全局确实是最优的，那么问题不就自然解决了，贪心给你个思路，万一是正确的呢？那你不是血赚嘛，比如你看上面的代码这么短不香嘛，，嘿嘿。
简单说明一下，理解是关键，严谨的证明请劳烦转移他处。。。
以本例为例，要在全局寻找是否存在递增的三元子序列，在一维遍历的时候，我们判断选择的策略便是基于当前的贪心策略，如果我们记录一个最小值在记录一个次小值，当找到比俩这都大的值的时候即成立，而事实上成立的条件不一定最小<次小<当前的三元组成立，比如，5，6，1，7，这个遍历下来之后，最小是1，次小仍然是6，但是最后一次并没有更新minf和mins，导致else成立，直接返回了true。而贪心策略认为返回true是根据1<6<7的判断，这估计也是你们之前的疑问之一吧，而事实它返回true是因为5<6<7欸，，。看下文。
也就是说，true成立不一定是因为一定能够找到这样一个俩个连小于关系，但事实上最终是能够证明这样一个策略推广至全局也是成立的，比如上面那个例子，minf更新为5的时候，mins并没有更新，而mins初始化是极大值，它这里没有更新说明前面已经找到了最小和次小之间的关系，而没有触发当前值小于mins的条件，即表明当前值确实是大于mins的，而这样的贪心策略能够保证前面一定存在minf < mins的关系，而当前值就大于mins，故返回true没有问题。
同样，那么股票问题也可以由此出发来看看。虽然我知道很多人看到股票类问题都是考虑动态规划的，而确实这一题依然可以用动态规划求解，为例让读者收获最大化，我这里也附上动态规划算法的解法吧，嘻~
基本思路
股票系列问题状态定义：
dp[i][k][0 or 1] 0 <= i <= n - 1, 1 <= k <= K n 为天数，大 K 为交易数的上限，0 和 1 代表是否持有股票。股票系列问题通用状态转移方程和 base case：
状态转移方程： dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]) dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]) base case： dp[-1][...][0] = dp[...][0][0] = 0 dp[-1][...][1] = dp[...][0][1] = -infinity特化到
k无限制的情况，状态转移方程如下：dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]) dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])解法代码
class Solution { public int maxProfit(int[] prices) { int n = prices.length; int[][] dp = new int[n][2]; for (int i = 0; i < n; i++) { if (i - 1 == -1) { // base case dp[i][0] = 0; dp[i][1] = -prices[i]; continue; } dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]); dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]); } return dp[n - 1][0]; } }
而这题的关键在于它不限制交易次数啊，我想买就买，想卖就卖，欸那我就很贪心，我就想找个最便宜的时候买，在找个最贵的时候卖呗。我想，正常人都会这样的吧，那再劳烦回去看看代码，思路就是这样的贪心策略的体现啊。要涨就买，要降就卖呗，反正我很贪心，欸就不能亏。
如果股票一直上涨，只需要找到股票上涨的最大值和股票开始上涨的最小值，计算他们的差就是这段时间内股票的最大利润。如果股票下跌就不用计算，最终只需要把所有股票上涨的时间段内的利润累加就是我们所要求的结果。
我想，这般，你应该，当然包括我在内，对贪心算法有了一次美好的相识了吧~
