C++ 代码

/*
    说实话，好像和dp真没什么关系
    思想：贪心
    1 2 3 4 和 1 2 3 6肯定是选前边的留下比较好，因为
    1 2 3 4 5 和 1 2 3 6 5 肯定是前边的那个最长上升子序列的长度更长。
    所以我们就每次加入一个数，就维护一下前i个数组成的序列中，最长子序列的长度，如果
    新加入的a[i]会使得序列末尾的数变小，就更新
    先放结论，以上升子序列的长度为自变量，每个长度下，对应的
    每个上升子序列末尾元素的最小值，作为因变量。可以知道，这样的函数
    是单调递增的。 因为假如q[3]>=q[4]的话，那么就在q[4]对应的那个序列中，选出来更小的第三个数，替换掉
    q[3]，此时q[3]就会更小。矛盾

*/
#include<iostream>
#include<algorithm>

using namespace std;

const int N=100010;

int q[N], a[N];//q[r]表示所有长度为r的上升序列中结尾元素的最小值

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;
        //利用二分，在q数组中寻找比a[i]小的最大的数
        while(l<r)
        {
            int mid=l+r+1>>1;//因为后边是l=mid,所以此处需要加上一
            if(q[mid]<a[i]) l=mid;
            else r=mid-1;
        }
        //len维护的是最大值，找到后，把a[i]接到q[r]后边了，所以更新len
        len=max(len,r+1);
        //更新操作，把上边样例中的6换成了4.
        //如果在q中找不到比a[i]更小的了，就开辟新的道路，证明len需要+1更新了
        q[r+1]=a[i];
        //当然，有可能在q数组中找不到比a[i]小的最大的值了，但是此时是一定可以找到的，
        //因为初始化q[0]=负无穷了，所以最差的情况也是二分找了一遍 r=0;
        //所以此时q[1]=a[i];代表长度为1的最长上升子序列的最小值是a[i],完成更新
    }

    printf("%d\n",len);

    return 0;
}