题目：300. 最长上升子序列
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
动态规划解法
值得注意的是，要区分子序列和子串的概念，子串要求连续，而子序列没有这个要求。
我们定义dp数组为dp[i]，它表示的含义是以第i个数即nums[i]结尾的最长上升子序列的长度。
对于每一个子序列，显然它的最小长度为1即包含自身一个元素，所以我们的基础状态dp[i] = 1。
接下来考虑状态转移方程：
假设我们求出了dp[i-1]，我们该如何求dp[i]呢？
既然要求是一个上升的子序列，那么必然需要从nums[0]到nums[i-1]找比nums[i]小的数作为子序列的前一项，从而构造出一个较长的子序列;想要达到最长子序列的目的，我们需要考虑所有可能的子序列，然后选出长度最大的即可。
我们可以写出：
求出以每个元素为结尾的最大上升子序列后，再遍历求出求大的子序列长度即为整个无序数组的最长上升子序列的长度。
代码为：
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
//dp数组全部初始化为1
vector<int> dp(nums.size(),1);
for(int i = 0;i < dp.size(); ++i){
for(int j = 0; j < i; ++j){
if(nums[j] < nums[i]){
dp[i] = max(dp[i],dp[j]+1);
}
}
}
//求出最大的序列长度
int res = 0;
for(int d:dp){
res = max(res,d);
}
return res;
}
};这样的解法算法时间复杂度为O(n^2)，做到这里已经可以了，但实际上时间复杂度还可降到O(nlogn)，也就是下面扩展介绍的二分解法。
二分查找解法
明眼看，总感觉二分解法和这道题扯不上关系，其实有一种纸牌游戏叫做patience game，它的玩法与最长上升子序列有关系，以这种游戏为名还衍生出了一种排序算法：patience sorting。
这个纸牌游戏也叫纸牌接龙，相信大家都玩过。
大佬的介绍：
首先，给你一排扑克牌，我们像遍历数组那样从左到右一张一张处理这些扑克牌，最终要把这些牌分成若干堆。
处理这些扑克牌要遵循以下规则：
只能把点数小的牌压到点数比它大的牌上；如果当前牌点数较大没有可以放置的堆，则新建一个堆，把这张牌放进去；如果当前牌有多个堆可供选择，则选择最左边的那一堆放置。
比如说上述的扑克牌最终会被分成这样 5 堆（我们认为纸牌 A 的牌面是最大的，纸牌 2 的牌面是最小的）。
为什么遇到多个可选择堆的时候要放到最左边的堆上呢？稍加观察可以发现，这样可以保证牌堆顶的牌有序（2, 4, 7, 8, Q）。
按照上述规则执行，可以算出最长递增子序列，牌的堆数就是最长递增子序列的长度，因为如果从每堆拿出一张牌，就可以形成一个递增子序列。又因为每堆牌的值是递减的，所以这个递增子序列是最长的。
我们只要把处理扑克牌的过程编程写出来即可。每次处理一张扑克牌不是要找一个合适的牌堆顶来放吗，牌堆顶的牌不是有序吗，这就能用到二分查找了：用二分查找来搜索当前牌应放置的位置，从而使算法时间复杂度降到O(nlogn)。
代码：
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
//cards记录每堆牌的最下面的牌
vector<int> cards(nums.size());
//牌堆数初始为0
int piles = 0;
//开始摆牌
for(int i = 0 ; i < nums.size(); ++i){
//要处理的牌
int poker = nums[i];
int l = 0, r = piles;
while(l < r){
int mid = l + (r - l)/2;
if(cards[mid] < poker){
l = mid + 1;
}
else if(cards[mid] >= poker){
r = mid;
}
}
//如果没找到合适牌堆，新建牌堆
if(l == piles) piles++;
//更新cards
cards[l] = poker;
}
//牌堆数即为最长公共子序列长度
return piles;
}
};
