LIS&LNDS

核心思想：

维护一个数组

f[k] = 长度为k的子序列最小结尾

LIS 最长上升子序列

vector<int> f;
for(int i=1;i<=n;i++){
    auto it=lower_bound(f.begin(),f.end(),a[i]);
    if(it==f.end())
        f.push_back(a[i]);
    else
        *it=a[i];
}

LNDS 最长不下降子序列

vector<int> f;
for(int i=1;i<=n;i++){
    auto it=upper_bound(f.begin(),f.end(),a[i]);
    if(it==f.end())
        f.push_back(a[i]);
    else
        *it=a[i];
}

最长不上升，最长下降

序列	关系	二分
严格上升	<	lower_bound
不下降	≤	upper_bound
严格下降	>	对 -a[i] 用 lower_bound
不升	≥	对 -a[i] 用 upper_bound

Dilworth的应用

最少不下降子序列覆盖链数=最长下降子序列大小