LIS最长上升（不下降）子序列

动态规划基础

线性DP做法：

dp数组 $f_i$ 记录以 $a_i$ 结尾的最长上升子序列的长度，在每轮枚举 $a_i$ 时，利用 $j$ 指针，从头扫描找到 $a_j<a_i$ ，这样 $a_i$ 可以作为 $a_j$ 的后续，接在 $f_j$ 的后面，时间复杂度为 $O(n^2)$

int n;
cin>>n;
vector<int> a(n+10,1),f=a;
int ans=0;
for (int i=1;i<=n;i++) cin>>a[i];
for (int i=2;i<=n;i++){
    for (int j=1;j<i;j++){
        if (a[i]>a[j])
            f[i]=max(f[i],f[j]+1);//状态转移
    }
    ans=max(f[i],ans);
}
cout<<ans;

注意需要初始化 $f$ 数组为 $1$ ，因为所有元素都和自身可以形成一个长度为 $1$ 的上升序列

状态转移方程为 $f_i=max(f_i,f_j+1)\impliedby a_i>a_j$

二分优化：

考虑第二层循环可以采用二分查找优化，于是需要维护一个序列 $b$ 记录当前最长上升子序列

int n;
cin>>n;
vector<int> a(n+10,1),f=a,b=a;
for (int i=1;i<=n;i++) cin>>a[i];
b[1]=a[1];
int len=1;
for (int i=2;i<=n;i++){
    if (a[i]>b[len]){
        b[++len]=a[i];
    }else{
        auto iter=lower_bound(b.begin()+1,b.begin()+len+1,a[i]);//二分查找
        *iter=a[i];
    }
}
cout<<len;

更新 $b$ 时存在两种情况：

• $a_i>b_{len}$ 即当前考虑的元素比维护的 $b$ 中最大元素还要大，那么 $a_i$ 一定可以续接在 $b$ 后面

• $a_i\le b_{len}$ 那么可以考虑替换 $b$ 中第一个大于等于 $a_i$ 的元素 $b_j$ ，替换后的 $b$ 一定不劣

  例如数组 1 2 4 1 3 4 ，x,y 分别代表 1,2 更新操作

x: 1 2 
x: 1 2 4 
y: 1 2 4 //1替换1
y: 1 2 3 //3替换4
x: 1 2 3 4 

len 变量可以记录答案，也就是最长上升子序列的长度，在做 y 操作时不会改变值

也就是说 len 存储了整个过程中历史存在的序列最长长度

相似的，最长不下降子序列也可以得出

int n;
cin>>n;
vector<int> a(n+10,1),f=a,b=a;
for (int i=1;i<=n;i++) cin>>a[i];
b[1]=a[1];
int len=1;
for (int i=2;i<=n;i++){
    if (a[i]>=b[len]){//可以取等
        b[++len]=a[i];
    }else{
        auto iter=lower_bound(b.begin()+1,b.begin()+len+1,a[i]);//二分查找
        *iter=a[i];
    }
}
cout<<len;