最长递增子序列（普通版/暴力版）

使用例题：最长上升子序列******。

题意：

     给你n个正整数组成的序列，求从原序列中按顺序取出一些数字排在一起，取出的数字必须是逐渐增大的。

数据量为5000。

代码详解：

     想要求解本题，最原始的思路即双重循环搜索，先遍历数组，再遍历每个值前的所有值（1~i-1），看当前值可以放在多少值的后面，利用dp数组记录每个数的最长长度，最后遍历循环，找出dp数组中的最大值。

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;

int n;
int maxn=0;
int a[N];
int dp[N];//存放当前数组能有的最大长度

int main(){
    cin >>n;
    for (int i=1;i<=n;i++)cin >>a[i];
    //遍历数组
    for (int i=1;i<=n;i++)
    {
    	//值自身有1长度
        dp[i]=1;
        //遍历当前值前的所有值
        for (int j=1;j<=i;j++)
        {
        	//当当前值大于该值时，说明可以放在该数后面
            //dp[j]+1，代表假设当前值放入该值队列时
            //dp[i]=max(dp[i],dp[j]+1)，作用是找出每个可放入数列中的最大值
            if (a[j]<a[i])dp[i]=max(dp[i],dp[j]+1);
        }
        //找出最大长度
        maxn=max(maxn,dp[i]);
    }
    cout <<maxn<<"\n";
}

最长递增子序列（二分版）

     学完了上题代码，如果你直接提交了，恭喜你喜提RE，因为使用了两个循环，注定了该代码的数据量，最多不能超过1e4，而上题代码的数据量为5000，所以做多拿到80分，想要拿到100分，就要使用其二分版本。

代码详解：

     二分的思路和暴力的不同之处在于，暴力的dp数组，记录的是每个数能达到的最大长度，而二分的eds数组，记录每个长度的最小值能是什么。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;

int n;
int id;
int len=0;
int a[N];
int eds[N];

int main(){
    cin >>n;
    for (int i=0;i<n;i++)cin >>a[i];
    for (int i=0;i<n;i++)
    {
    	//查找第一个大于或等于a[i]的数的地址
        id=lower_bound(eds,eds+len,a[i])-eds;
        //当查找的值大于数组的长度时，说明该数值比所有数组中所有值都大，加入新长度
        if (id>=len)eds[len++]=a[i];
         //能找到，则对eds[i]进行替换
        else eds[id]=a[i];
    }
    cout <<len<<"\n";
}

     了解完代码后，细讲为什么可以这样实现。

     首先利用图表进行演示eds数组中的值的推演过程，假设存在数组a=[1,9,2]。

1. 每列代表当处于i时eds的值
2. 【】代表被替换
3. {}代表当前长度的值

     如表所示，eds数组中表现的值只是缩写，其代表的是整个队列的顶点，即队列中的最大值。因此当存在超出eds[len]的值时，代表该值比所有的值都大，可以增加队列长度len++，而代码中的替换步骤相当于重复上一步，a[i]的值比前一个队列的最大值要大，使队列长度增加，所以顶替原先的数值。因此在eds数组中使用lower_bound()查找出的第一个大于等于a[i]的值。

     最长不下降子序列同理，从原先查找最大，改为查找最小，维持最小，所以只要替换查找方式为upper_bound()即可。

最长递增子序列（二维递增版）

使用例题：链接最长数对链******。

题意：

     给你n个数组对数组pairs，假设数组对x[a,b]和y[c,d]，其中a<b，有一种链接方式，当且仅当b<c时，达成链接，现要求pairs能形成的最大链接长度。

代码详解：

     二维递增版与二分的差别，即将查找的值和更新进行了更改。

int findLongestChain(vector<vector<int>>& pairs) {
        const int N=1e6+10;
        int id;//记录每次查找到的值
        int eds[N];//记录每个长度的最小值
        int len=0;//eds长度初始为0
        
        //题目限定，为了能满足b<c的条件，使pairs数组进行从小到大排序
        //sort函数默认从小到大排，对数组对而言，当第一个数相同时，第二个数的比较也是从小到大
        sort(pairs.begin(), pairs.end());
        
        /*
        sort排序的定义：
        sort(envelopes.begin(),envelopes.end(),[](const auto& e1,const auto& e2){
		    return e1[0]<e2[0] || (e1[0]==e2[0] && e1[1]>e2[1]);
	    });
        */
        
        for (auto p:pairs)
        {
        	//x代表a,y代表b
            int x=p[0],y=p[1];
            //因为b<c才能链接，所以查找的是x值，替换和记录的是y值
            id=lower_bound(eds,eds+len,x)-eds;
            if (id>=len)eds[len++]=y;
            //注意选择更小的值进行替换，对二维而言，y值越小，越利于连接
            else eds[id]=min(eds[id],y);
        }
        return len;
    }