当前位置：首页 > news >正文

最长上升子序列(LIS)

news 来源：原创 2024/5/21 15:24:33

最长上升子序列 $(L I S)$ ，就是求一个序列的最长子序列，满足子序列中的元素严格单调递增。

一般求法

设 $f_i$ 表示前 $i$ 个元素中包含第 $i$ 个元素的最长上升子序列的长度。则可列出DP式：

$f_i=\min f_j+1$ ，其中 $j$ 满足 $1\leq j<i$ 且 $a_i>a_j$

这样求LIS最简单，时间复杂度为 $O(n^2)$

code

#include<bits/stdc++.h>
using namespace std;
int n,a[10005],f[10005];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
    f[1]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++)
        if(a[i]>a[j]) f[i]=max(f[i],f[j]+1);
    }
    printf("%d",f[n]);
    return 0;
}

特殊求法

对于一个序列，假设已经求出了前 $i$ 个数的最长上升子序列，在加入第 $i + 1$ 个数时，在当前数列中找到第一个大于等于它的数。如果有，则用新加入的数替换；否则将新加入的数放在队尾。

我们来一个例子：

对于序列 $1, 2, 5, 7, 4, 5, 3$

加入第一个元素 $1$ ，目前最长上升子序列为 $1$
加入第二个元素 $2$ ，目前最长上升子序列为 $1, 2$
加入第三个元素 $5$ ，目前最长上升子序列为 $1, 2, 5$
加入第四个元素 $7$ ，目前最长上升子序列为 $1, 2, 5, 7$
加入第五个元素 $4$ ，目前最长上升子序列为 $1, 2, 4, 7$
加入第六个元素 $5$ ，目前最长上升子序列为 $1, 2, 4, 5, 7$
加入第七个元素 $3$ ，目前最长上升子序列为 $1, 2, 3, 5, 7$

虽然最终得到的序列不是最长上升子序列，但该序列的长度与最长上升子序列相同。如果题目只是求LIS的长度，则用这个方法可以解决，而且时间复杂度为 $O (n l o g n)$ 。这个解释起来比较繁琐，但仔细想想，多试几个例子就可以理解它是可行的。

code

#include<bits/stdc++.h>
using namespace std;
int n,l=1,x,a[10005];
int main()
{
    scanf("%d",&n);
    scanf("%d",&a[l]);
    for(int i=2;i<=n;i++){
        scanf("%d",&x);
        if(x>a[l]) a[++l]=x;
        else{
            int t=lower_bound(a+1,a+l+1,x)-a;
            a[t]=x;
        }
    }
    printf("%d",l);
    return 0;
}