还记得大约两年前我写过一篇博客《最长严格上升子序列》，里面使用了一种$ O(n^2) $的算法来求解其最大长度，两年之后，我们继续讨论这个问题。但是这一次，我们介绍一种$ O(nlogn) $的算法。

直接上代码，用注释的方式讲解

#include <iostream>
#define MAXN 100000
using namespace std;

int a[MAXN];
int dp[MAXN];
int count,maxnum;
int ans;

int lowbit(int x) {
    return x&(-x);
}
//就是一个树状数组lowbit函数
void add(int x,int data) {
    for(int i=x;i<=maxnum;i+=lowbit(i))
        dp[i] = max(dp[i],data);
}
//在这个函数里，我们维护一个树状dp数组，向后更新
//因为我们是向后增加这一个链的长度，由低点影响高点
//如果不这么做，可能会使结果变大（data往往比dp数组中低位的数据大）
int query(int x) {
    int r = 0;
    for(int i=x;i>=1;i-=lowbit(i))
        r = max(dp[i],r);

    return r;
}
//返回小于等于x的数的个数的最大值
int main() {
    ios::sync_with_stdio(false);//读入优化

    int t;
    while(cin>>t) {
        a[++count] = t;//输入数据
        maxnum = max(maxnum,t);//求区间最大范围
    }

    --count;//count最好减1防止后面忘记

    for(int i=count;i>=1;--i) {
        //因为我们的add函数是向后更新数据的，所以这里倒序加入，其实也就是把问题反了过来
        //维护的其实是一个最长上升子序列的树状数组
        int q = query(a[i])+1;//查询小于等于a[i]的数的个数,尝试把当前值加入
        add(a[i],q);
        ans = max(ans,q);//当前尝试的值与答案比较取优解
    }

    cout<<ans<<endl;

    return 0;
}

同时我们还可以根据Dilworth定理求元素不重复使用的不上升子序列（也就是子链元素和等于母链元素和）的个数。

也就是反过来求这个序列的不下降子序列的最大长度，同样用树状数组维护，只是这一次我们正序输入数据，算法复杂度还是$ O(n\log{n}) $。

同样，求最长不下降子序列也很好实现——只需要询问a[i]-1就行。