最长上升子序列LIS

发表于 | 分类于

介绍

最长上升子序列问题，也就是Longest increasing subsequence，缩写为LIS。是指在一个序列中求长度最长的一个上升子序列的问题，是动态规划中一个相当经典问题。在这里我们可以看到，这个上升实质上就是一个对<进行定义的过程，所以我们求解的其实是一类问题，也就是在给定序列中求解长度最长的符合某一性质的子序列的问题。

解法一

状态设计：F[i]代表以A[i]结尾的LIS的长度
状态转移：F[i]=max{F[j]+1}(1<=j< i,A[j]< A[i])
边界处理：F[i]=1(1<=i<=n)
时间复杂度：O(n^2)
PS(理解dp最简单的方法：画表，自行推理)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int a[maxn],dp[maxn];
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		dp[i]=1;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<i;j++){
			if(a[j]<a[i]) dp[i]=max(dp[i],dp[j]+1);
		}
	}
	int maxx=0;
	for(int i=1;i<=n;i++) maxx=max(maxx,dp[i]);
	printf("%d\n",maxx);
	return 0; 
}

解法二

贪心加二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
const int INF=0x7f7f7f7f;
int a[maxn],dp[maxn];
int binary_search(int l,int r,int x){//二分查找第一个大于等于x的元素
	while(l<=r){
		int mid=(l+r)>>1;
		if(dp[mid]<=x) l=mid+1;
		else r=mid-1; 
	}
	return l;
}
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		dp[i]=INF;//初始化为无穷大
	}
	int pos=1;
	dp[1]=a[1];
	for(int i=2;i<=n;i++){
		if(a[i]>dp[pos]) dp[++pos]=a[i];
//		else dp[lower_bound(dp+1,dp+pos+1,a[i])-dp]=a[i];
//lower_bound(a,a+n,x)函数 返回从数组a到a+n中第一个>=x的元素地址
		else dp[binary_search(1,pos,a[i])]=a[i];
//也可以自己写二分查找。
	}
	printf("%d\n",pos);
	return 0;
}

解法三

用树状数组维护，降低复杂度。
PS(我写完后发现这个方法将相等的也计算在其中)。
不知道有没有人能去除掉相等，是我太菜了，QWQ.
维护每个数的序列也就是第几个数，然后查询其前面的最长上升子序列，然后更新其后的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int n,dp[maxn];
struct point{
	int x,id;
	bool operator < (const point &a) const{
		return x<a.x||(a.x==x&&a.id>id);
	}
};
int lowbit(int x){
	return x&(-x);
}
int query(int x){
	int sum=0;
	while(x){
		sum=max(sum,dp[x]);
		x-=lowbit(x);
	}
	return sum;
}
void modify(int x,int y){
	while(x<=n){
		dp[x]=max(dp[x],y);
		x+=lowbit(x);
	}
}
point a[maxn];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i].x);
		a[i].id=i;
	}
//	for(int i=1;i<=n;i++) printf("%d %d\n",a[i].x,a[i].id);
//	printf("\n");
	sort(a+1,a+n+1);
//	for(int i=1;i<=n;i++) printf("%d %d\n",a[i].x,a[i].id);
	int ans=0;
	for(int i=1;i<=n;i++){
		int maxx=query(a[i].id);
		modify(a[i].id,++maxx);
		ans=max(ans,maxx);
	}
	printf("%d\n",ans);
	return 0;
}

解法四

随后我查了相关的博客后，发现换个思维就可以排除相等的情况。
即维护每一个刚输入的值，查询其前面的最长的上升子序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int n,dp[maxn];
int lowbit(int x){
	return x&(-x);
}
int query(int x){
	int sum=0;
	while(x){
		sum=max(sum,dp[x]);
		x-=lowbit(x);
	}
	return sum;
}
void modify(int x,int y){
	while(x<=maxn){
		dp[x]=max(dp[x],y);
		x+=lowbit(x);
	}
}
int main(){
	scanf("%d",&n);
	int ans=0;
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		x++;//因为树状数组从1开始，每次查询x-1以及前面的最大值
		int maxx=query(x-1)+1;
		ans=max(ans,maxx);
		modify(x,maxx);
	}
	printf("%d\n",ans);
}

不过解法三和四都有一定的局限性，只能所有数都是>=1的正整数时才能用，不过这种思维可以用在好多地方。
如果存在负数的情况，用方法二是最好的。