最长上升子序列Ⅱ(单调性优化+二分查找)（O（nlogn））

原题链接

N=100000

优化算法Ⅰ：

利用DP求取针对最末位的元素的最长的子序列，如果子序列的长度相同，那么最末位的元素较小的在之后会更优（因为末位更小更加有机会接新的序列）

因此重新定义集合：

具体步骤：初始化dp[i],每个设置为INF，从头往后插入一个a[j],比较大小，dp[i]=min(d[i],a[j])进行更新得到单调递增序列，因为递增序列，所以可以二分查找更新位置

#include <iostream>
#include <algorithm>

using namespace std;

const int N=1e5+10;
const int INF=0x3f3f3f3f;

int n;
int a[N],dp[N];

int main()
{
    cin>>n;
    fill(dp,dp+n,INF);
    for(int i=0;i<n;i++)
        cin>>a[i];

    for(int i=0;i<n;i++)
        *lower_bound(dp,dp+n,a[i])=a[i];//注意lower_bound返回的是指针，在返回处直接赋值a[i]

    printf("%d\n",lower_bound(dp,dp+n,INF)-dp);//第一个无穷处-0处=长度

    return 0;
}