独特的、简单的理解方式

这里给大家介绍一种全新的理解这道题的方式~~

首先引入一些我自创的、针对这道题目的一个概念： 数的等级

定义：倘若在一个考虑先后顺序的数组中，那我们认为下标更小的数为更前的数。在此条件下，一个数的等级可以被描述为，该数的等级等于在它前面且大小严格比它小的数的数目+1。并且我们约定，数的最低等级为1级。

举个例子，比如一个数前面有k个数比它小，那么它的等级就是k+1级。

那么通过我们的定义，我们就可以转化题意。题中让我们求最长的上升子序列，那么从我们的定义出发，就可以转化成，求数组中数的最大等级。（原因参考前面的定义）

那么我们接下来要做的事情那就是求一下我们当前数组中数的最大等级就好了。

具体的如何实现呢？

我们开一个等级数组，用来存放我们每一个等级中的数（这里只需要存放最小的数即可，稍后会给大家解释），$grade$，它的下标用来表示我们的等级。$grade$[1]就表示1级，$grade$[2]就代表2级。

那么根据我们生活的经验可以知道，等级越高的数，大小必然越大，所以 $grade$ 数组必然是单调递增的。

那么我们如何去求每个数的等级呢？

根据等级大小关系知道，等级越高，数就越大。所以我们要确定一个数的等级，就只需要找出来在它前面的，且严格比它小的数的集合中，最大的那个数，那么我们该数的等级就等于我们找出的那个数的等级+1。（如果有疑问可以再看一下我们的定义）

比如我们的样例 3 1 2 1 8 5 6

如果我们要求3的等级，那就找一下在它前面的且严格比它小的，最大的数，是哪一个，由于在它前面没有数，那么它的等级就是1。

以此类推，可知该数组中各个数的等级分别为 1 1 2 1 3 3 4

故最大等级为4，那么我们的答案也就是4

那具体是如何实现的呢？

根据上述的求等级的方式，我们对于每个数，都在 $grade$ 数组里面找到严格比它小的、最大的那个数，然后我们当前数的等级就是它的等级（也就是它在 $grade$ 数组中的下标）+1。同时，我们用它来更新它所在的等级的那个数。

比如我们当前找到的是 $grade$[k]，那么我们就把 $grade$[k+1]更新为当前遍历到的数（记为a[i]）。

那为什么可以更新呢？

这里其实存在一个性质，每个等级的数如果都尽可能的小，那么我们最终的最高的等级才是尽可能的大。

这个比较好理解。

根据我们上述寻找的方式，我们找到的是严格比我们小的且最大的数，也就是$grade$[k]，那么也意味着我们$grade$[k+1]肯定大于等于a[i]，那么根据我们上述的性质，就可以把我们的$grade$[k+1]更新为a[i]。这样子就可以使得我们最高的等级尽可能的高。

而由于我们的 $grade$ 数组是单调递增的（前面解释过），所以我们在寻找比我们严格小的、最大的那个数的时候，可以利用二分来找。

那么最后我们的答案是什么呢？

通过上面的分析可以知道，其实最高等级就是 $grade$ 数组的长度，不过是从1开始计算的。因为我们 $grade$数组的下标就代表等级，那么我们最高用到了哪个下标那么我们的最高等级就是哪个。

好，带着大家用我的理解方式理解了一下这个题目，虽然换了一种理解方式，但是代码总体还是一样的。

代码也有注释哦！

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>

#define in(x) scanf("%lld",&x);
#define out(x) printf("%lld",x);
#define f(x,n,t) for(int i=x;i<=n;i+=t)

using namespace std;

const int N=100010;

typedef long long LL;

LL a[N];

LL n;

LL grade[N];

int main()
{
    in(n);

    f(1,n,1)in(a[i]);

    LL highest=0;//直接定义一下我们当前最高等级是多少，最后就不用再去算grade数组的长度了

    grade[0]=-1e18;//防止出现第0级的数

    f(1,n,1)//从前到后遍历每一个数，计算一下等级，并且更新一下每个等级中的最小数
    {
        LL l=0,r=highest;

        while(l<r)//二分一下
        {
            LL mid=l+r+1>>1;

            if(a[i]>grade[mid])//由于是严格小的，所以这里不能取等号
            l=mid;
            else
            r=mid-1;
        }
        //这个二分模板还是要用对的，细节要处理好，不然会出错
        grade[l+1]=a[i];

        if(l+1>highest)//更新一下当前的最高等级
        highest=l+1;
    }

    out(highest);//输出我们的最高等级

    return 0;
}