目录
一、最长递增子序列
二、递增的三元子序列
三、最长连续递增序列
四、买卖股票的最佳时机
五、买卖股票的最佳时机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;
else
left = 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;
else
return 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;
}
};