贪心算法（二）

一、最长递增子序列

二、递增的三元子序列

三、最长连续递增序列

四、买卖股票的最佳时机

五、买卖股票的最佳时机II

一、最长递增子序列

最长递增子序列

拿到这道题，我们最先想到的就是用动态规划的方法去解决它。使用动态规划的方法，我们只需要考虑元素能否接在他之前的某个元素后面，从而形成递增子序列。

而我们可以根据动态规划算法对其进行优化。我们并不需要关心这个递增子序列长什么样子，我们仅关心递增子序列的最后一个元素是什么。

贪心策略：

从前到后扫描每一个元素，当扫描第一个位置的元素时候，其实我们得到一个长度为1 的序列的最后一个位置的元素。如下图：

扫描到9的时候发现，9是接不到10后面的，所以9这个元素单独形成一个长度为1的序列，现在又找到一个长度为1的序列最后一个元素是9。此时贪心策略就来了，当我发现长度为1递增子序列有两个的时候，较大的就没有必要存了。如下图：

扫描2的时候，2是接不到9后面的，所以2这个元素单独形成一个长度为1的序列，并且2小于9，所以不存9，存2。如下图：

扫描5的时候，我们其实有两种策略，第一种是让5单独形成一个长度为1的序列，第二种是让5拼到2的后面形成一个长度为2的序列。此时我们贪心选择第二种策略。因为要找最长递增子序列。如下图：

扫描到3的时候，3可以接在2的后面，但不能接在5的后面，所以递增序列长度为2的位置存较小的3。如下图：

扫描到7的时候，7可以接在2的后面，也可以接在3的后面，因为要找最长的递增序列，所以将7放在3的后面，形成长度为3的递增序列。如下图：

扫描到101的时候，101可以接在2的后面，也可以接在3的后面，也可以接在7的后面，因为要找最长的递增序列，所以将101放在7的后面，形成长度为4的递增序列。如下图：

扫描到18的时候，18可以接在2的后面，也可以接在3的后面，也可以接在7的后面，但无法接在101的后面，所以递增序列长度为4时，最后位置的元素存较小的18。如下图：

至此，所有的元素都已经扫描完毕了，最终得到的最长递增子序列的长度是4。

我们在确定一个元素所在的位置的时候，可以使用二分查找，就不需要一一和前面的元素进行比较了。

解题代码：

class Solution 
{
public:int lengthOfLIS(vector<int>& nums) {//算法>贪心算法vector<int> ret;ret.push_back(nums[0]);int m = nums.size();for(int i = 1; i < m; i++){int num = nums[i];if(num > ret.back()){ret.push_back(num);}else{int left = 0, right = ret.size()-1;while(left < right){int mid = left + (right-left) / 2;if(ret[mid] >= num)right = mid;elseleft = mid+1;}ret[left] = num;}}return ret.size();}
};

二、递增的三元子序列

递增的三元子序列

贪心策略：

这道题的贪心策略其实和第一题是一样的。但是我们只需要找长度为3的子序列。并且，我们只需要找到一个结果就可以返回了，不用去找完所有的三元子序列。

解题代码：

class Solution 
{
public:bool increasingTriplet(vector<int>& nums) {int m = nums.size();if(m < 3)return false;vector<int> ret;ret.push_back(nums[0]);for(int i = 1; i < m; i++){if(ret.back() < nums[i])ret.push_back(nums[i]);else{for(int j = 0; j < ret.size(); j++){if(ret[j] >= nums[i]){ret[j] = nums[i];break;}}}if(ret.size() == 3)return true;}if(ret.size() == 3)return true;elsereturn false;}
};

三、最长连续递增序列

最长连续递增序列

贪心策略：

用指针 i 固定一个数。然后再来一个指针 j，让这个指针 j 向后移动，去找以 i 位置为起点的最长的连续递增序列。只要 j 位置元素比 j-1 位置元素大，j就往后移动，当 j 位置元素比 j-1 位置元素小就结束，此时就找到了以 i 位置为起点的最长连续的递增序列。

然后，i 移动到 j 位置，以 j 位置为起点，j 向后移动往后找，去找下一个递增子序列。

解题代码：

class Solution 
{
public:int findLengthOfLCIS(vector<int>& nums) {int m = nums.size();int len = INT_MIN;for(int i = 0; i < m;){int j = i+1;while(j < m && nums[j-1] < nums[j])j++;len = max(len, j-i);i = j;}return len;}
};

四、买卖股票的最佳时机

买卖股票的最大时机

题目明确要求：股票只能在某一天买入，并在未来某一天卖出。我们先来看看暴力解法。

我们按顺序固定某一天将股票卖出，那么我们就需要在它之前去找到买入股票的时间。

题目要求利润最大，因为我们固定的是卖出，所以收入是知道的，为了利润最大，我们需要在卖出之前找买入股票花费最少的时间。那么，我们就需要从前往后去遍历，使卖出收入减去买入支出的值最大，也就是找股票价格最小的时间。

暴力解法的时间复杂度是 O(n^2)。

贪心策略：

暴力解法的时间复杂度慢，慢就慢在，我们在找买入股票花费最少的时间时，是从前往后遍历的。

而如果我们使用一个变量来记录在这之前的股票价格的最小值，我们就不再需要从前往后遍历了。

解题代码：

class Solution 
{
public:int maxProfit(vector<int>& prices) {// 算法>贪心算法int maxprofit = INT_MIN;int minprice = prices[0];for(int i = 1; i < prices.size(); i++){maxprofit = max(maxprofit, prices[i] - minprice);minprice = min(minprice, prices[i]);}return maxprofit < 0 ? 0 : maxprofit;}
};

五、买卖股票的最佳时机II

买卖股票的最佳时机II

贪心策略：

这道题允许我们多次买卖股票，但是每次只能持有一支股票。

如下图，我们只要找到所有能够获得正收益的一段，就可以将其利润算上。只要是上升的一段区域，我们都可以将其利润拿到。最后的结果就是最大利润。

解题代码：

class Solution 
{
public:int maxProfit(vector<int>& prices) {// 算法>贪心算法int m = prices.size();int maxprofit = 0;for(int i = 0; i < m;){int j = i+1;while(j < m && prices[j-1] < prices[j])j++;if(prices[j-1] > prices[i])maxprofit += prices[j-1]-prices[i];i = j;}return maxprofit;}
};