dp

$O(nlogn)$

C++ 代码

/*
1.dp[i]数组存储的是长度为i的 严格递增的子序列 的最后一个元素的值中最小的值
dp[i]保证存储长度为i的严格递增的子序列最后一个元素的最小值
存最小值的原因是:
假设dp[i]存的最小值min，一般值为x

对于序列后面的值，如果它能接在x后面，就一定能接在min后面，而且接在min后面的选择会更大；
能接在min后面的，不一定能接在x后面

2.dp[i]的值一定是符合单调递增的：
反证法：
如果存在dp[i-1]>dp[i]
则有以dp[i]结尾的严格递增子序列的倒数第二个元素为x,显然x<dp[i]

则：
以x结尾的严格递增子序列的长度为i-1
以dp[i-1]结尾的严格递增子序列长度为i-1,且x<dp[i-1]
又因为dp数组存储的是最小值，
  故：dp[i-1]=x;
  x<dp[i];
  dp[i]<dp[i-1]=x
  矛盾

*/
#include<iostream>
#include<cstring>
#define N 100010
using namespace std;
int nums[N];
int dp[N];
int main(){
    int n;
    cin>>n;

    for(int i=1;i<=n;++i)cin>>nums[i];
    memset(dp,0x3f,sizeof dp);
    dp[0]=-0x3f3f3f3f;
    int len=0;
    for(int i=1;i<=n;++i){
        int l=0;
        int r=len;
        while(l<r){
            int mid=(l+r+1)>>1;
            /*
            去找必nums[i]小的，最大值，即使存在nums[i],也不去找
            1.如果找到一个和nums[i]相等的值它的长度为len，则要去取更新dp[len+1]的最小值，这样的后果会导致dp[len+1]的值为nums[i],子序列就会出现相等的情况了


            */
            if(dp[mid]<nums[i])
                l=mid;
                else 
                r=mid-1;
        }
        dp[l+1]=min(dp[l+1],nums[i]);
        //如果找到l+1已经大于len，则说明找到一个更长的子序列的长度，则更新len
        len=max(len,l+1);

    }

    cout<<len<<endl;


    return 0;
}