动态规划-最长上升子序列(LIS)

时间:2021-03-13 16:51:24

时间复杂度为〇(nlogn)的算法,下面就来看看。

我们再举一个例子:有以下序列A[]=3 1 2 6 4 5 10 7,求LIS长度。

我们定义一个B[i]来储存可能的排序序列,len为LIS长度。我们依次把A[i]有序地放进B[i]里。(为了方便,i的范围就从1~n表示第i个数)

A[1]=3,把3放进B[1],此时B[1]=3,此时len=1,最小末尾是3

A[2]=1,因为1比3小,所以可以把B[1]中的3替换为1,此时B[1]=1,此时len=1,最小末尾是1

A[3]=2,2大于1,就把2放进B[2]=2,此时B[]={1,2},len=2

同理,A[4]=6,把6放进B[3]=6,B[]={1,2,6},len=3

A[5]=4,4在2和6之间,比6小,可以把B[3]替换为4,B[]={1,2,4},len=3

A[6]=5,B[4]=5,B[]={1,2,4,5},len=4

A[7]=10,B[5]=10,B[]={1,2,4,5,10},len=5

A[8]=7,7在5和10之间,比10小,可以把B[5]替换为7,B[]={1,2,4,5,7},len=5

最终我们得出LIS长度为5。但是,但是!!这里的1 2 4 5 7很明显并不是正确的最长上升子序列。是的,B序列并不表示最长上升子序列,它只表示相应最长子序列长度的排好序的最小序列。这有什么用呢?我们最后一步7替换10并没有增加最长子序列的长度,而这一步的意义,在于记录最小序列,代表了一种“最可能性”。假如后面还有两个数据8和9,那么B[6]将更新为8,B[7]将更新为9,len就变为7

lower_bound(a,a+n,i)函数 返回从数组a到a+n中第一个>=i的元素地址

upper_bound(a,a+n,i)函数 返回从数组a到a+n中第一个>i的元素地址

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=;
int a[MAXN];
int d[MAXN];
int main()
{
int n;
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
d[]=a[];
int len=;
for(int i=;i<=n;i++)
{
if(a[i]>d[len])
d[++len]=a[i];
else
{
int j=lower_bound(d+,d+len+,a[i])-d;
d[j]=a[i];
}
}
printf("%d\n",len);
return ;
}