最长上升子序列(LIS)

最长上升子序列,全称Longest Increasing Sequence,简称LIS,在计算机科学上是指一个序列中最长的单调递增的子序列(百度百科)。这个序列不一定是连续的。

之前说过,动态规划就是把一个问题分成一大堆子问题,对这些子问题求解,最后求解出这个问题。如何求最长升序列?我们可以想到,随便取一个数字a[i](当然是在序列里),要是我们知道a[i]之前的且最后一个数据比a[i]小的最长上升子序列长度该多好!直接+1就是以i为结尾的最长上升子序列长度。那么要知道之前的最长升序列长度,就要按照同样的方法找之前的之前……显然是动态规划。

一、普通的DP方法

定义F[i]表示以队列中第i个元素(a[i])为结尾(其中第i个元素必取)的最长上升子序列长度。转移方程:

F[i]=max(F[i],F[j]+1);  (a[i]>a[j] && i>j)

这样求时间复杂度O(N²)。

二、二分优化的方法

另一种求法是二分优化。维护一个单调不降的序列que,同样定义F[i]为以队列中第i个元素(a[i])为结尾(其中第i个元素必取)的最长上升子序列长度。有个贪心的想法:我们要让最长上升子序列尽量长,就要让序列中最后一个元素尽量小(这样才能让后面元素可以加入的可能性更大),所以对于每个数字a[i],在序列中用二分找一个大于a[i]且最接近a[i]的数字替换,这样并不会影响序列的长度,也能保证解最优。如果序列里所有数字都小于a[i]就将其加入序列尾部。

这里有个问题:替换了序列中的元素,似乎并不能保证替换位置之后的元素在原序列a[i]之后出现?举个栗子:

维护的序列(que数组):1 3 5 7 9
原序列(a数组):1 3 5 7 9 4 10(i=6,即现在要处理4这个数字)
本次替换后:1 3 4 7 9

很显然,原序列里1 3 4 7 9并不符合要求(没按照顺序来)。我们接着往下看:下一步,处理6,替换了7,序列变成了1 3 4 7 9 10,长度是6,正确答案是1 3 5 7 9 10,长度也是6,和答案一样!

其实替换不会减小序列长度,只会增加序列长度;如果之前把序列中某个元素替换成a[i],那么之后新加入序列的元素(非替换)肯定都在a[i]之后!que序列并不是真正的最长上升序列,但是长度一定与真正的最长上升序列相等!这么优化可以把时间复杂度优化到O(Nlog2(N))。

代码(新鲜出炉的!!!):

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=100005;
int n,a[maxn],que[maxn],len=0;
inline int read(){
 int ret=0,f=1;char ch=getchar();
 while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
 while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
 return ret*f;
}
inline int find(int x){
 int L=1,R=len;
 while (L<=R){
  int mid=((R-L)>>1)+L;
  if (que[mid-1]<x&&x<que[mid]) return mid; else
  if (x<que[mid]) R=mid-1; else
  L=mid+1;
 }
 return 0;
}
int main(){
 n=read();
 for (int i=1;i<=n;i++){
  a[i]=read();
  int fd=find(a[i]);
  if (fd==0) que[++len]=a[i]; else que[fd]=a[i];
  }
 printf("%d\n",len);
 return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注