思路:

坐标轴4表示的是序列长度为4时,序列结尾的最小值
例如 1 2 4 7 和1 2 4 9
这时候选哪个比较好?如果不清楚,那么插入8
第一个 1 2 4 7 8
第二个 1 2 4 9 8
明显第一个方案要更好一点,代码中用数组q[r]来表示长度为r的序列长度结尾的最小值
所以此时q[4]=7更妥当一些
(暂时简陋表述,具体有空时会补上)

样例理解:

本体是基于贪心的思想来做的,具体样例过程如下:
n=10
a 3 1 2 0 8 5 6 4 7 9
start:

q: 3
len=1

1比3要小,r=0,q[r+1]=q[1]=1;
q:1
len=1

2比1大,r=1,所以len=r+1,q[r+1]=q[2]=2;
q:1 2
len=2

没有比0小的,r=0,q[r+1]=q[1]=0;
q:0 2

8 ,8比2大,r=2,len=max(len,r+1)=3,q[r+1]=q[3]=8
q:0 2 8

5 ,5比2大,r=2,len=max(len,r+1)=3,q[r+1]=q[3]=5;
q:0 2 5

6 ,6比5大,r=3,len=max(len,r+1)=4,q[r+1]=q[4]=6;
q: 0 2 5 6

4 ,4比2大,r=2,len=max(len,r+1)=4,q[r+1]=q[3]=4
q: 0 2 4 6

7 ,7比6大,r=4,len=max(len,r+1)=5,q[r+1]=q[5]=7
q: 0 2 4 6 7

9 ,9比7大,r=5,len=max(len,r+1)=6,q[r+1]=q[6]=9
q: 0 2 4 6 7 9

#include<iostream>
#include<algorithm>

using namespace std;

const int N=100010;

int q[N],a[N];

int main()
{
    int n;
    scanf("%d",&n);

    for(int i=1;i<=n;i++) scanf("%d",&a[i]);

    q[0]=-2e9;//用于加入第一个数
    int len=0;//前i个数中最大的最长上升子序列的值
    for(int i=1;i<=n;i++)
    {
        int l=0,r=len;
        while(l<r)//二分寻找在q数组中比a[i]小的最大的值
        {
            int mid=l+r+1>>1;
            if(q[mid]<a[i]) l=mid;
            else r=mid-1;
        }
        len=max(len,r+1);//如果a[i]比q[len]大的话,那么最大的最长上升子序列的值应当加1
        q[r+1]=a[i];
        /*
        q[r]是比a[i]小的最大的值,所以q[r+1]就一定大于a[i],此时把a[i]插入到q[r]的后面,
        因为a[i]<q[r+1],所以插入到q[r]的后面后,q[r+1]应当等于a[i]
        */
    }

    printf("%d",len);

    return 0;
}