浅谈LIS的两种写法

Just_Starlet · 2025-06-19 22:10:15 · 题解

前言

因为题解区就一篇时间复杂度为 O(n^2) 的算法，
而讨论区里不少都在提 O(n\log n) 的优化，
所以我写了一篇。

分析

兵马未动，定义先行
最长上升子序列（Longest Increasing Subsequence ，简称 LIS ），是指在给定的一个序列中，取出若干个数按原顺序构成子序列，使得其单调递增（即后一项大于前一项）并且其长度尽可能大。

Solution 1: 未优化的朴素dp

显然这是一道动态规划版子题。
定义 f_i 为以第 i 个数结尾的最长上升子序列的长度。
分类讨论：

• 若第 i 个数是唯一一项，则 f_i \gets 1
• 若第 i 个数接在第 j 个数后面，则 a_i>a_j ，枚举 j 可得到转移方程： f_i=\max_{j<i,a_i>a_j}\{f_j+1\}

综合两式可得

Code 1 :

#include<bits/stdc++.h>
using namespace std;
#define N 5005
int n,a[N];
int f[N],len;
int read(){
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    f[1]=1;len=1;
    for(int i=2;i<=n;i++){
        f[i]=1;
        for(int j=1;j<i;j++) if(a[i]>a[j]) f[i]=max(f[j]+1,f[i]);
        if(len<f[i]) len=f[i];
    }
    printf("%d",len);
    return 0;
}

Solution 2: 贪心+二分

然而，前一种算法的 O(n^2) 复杂度是很难说过去的。
回想一下刚才的转移方程：

有没有优化的余地呢？
不难发现，长度为 l 的序列只能由长度为 l-1的序列转移而来。
故维护数组 lst_i 表示长度为 i 的上升子序列的最小末项。
每次转移 f_i 时二分查找小于 a_i 的最大 lst_j。