最长上升子序列

最长上升子序列

题目描述

给定一个长度为 \(n\) 的数列 \(a\)，求其最长上升子序列长度

DP \(O(n^2)\)

\(f[i]\) 表示以 \(i\) 结尾的最长上升子序列

显然有 \(f[i]=max(f[i],f[j]+1)\)

其中 \(1\leq i \leq n,1\leq j\leq i,f[0]=0,f[n]\) 即为所求

code

for(int i=1; i<=n; ++i)
	for(int j=1; j<i; ++j)
		if(a[j]<a[i])
			f[i]=max(f[i],f[j]+1);

一种 \(O(n\log n)\) 的做法

\(f[i]\) 表示最长上升子序列的第 \(i\) 项的值

\(len\) 表示序列长度，\(len\) 即为所求

code

f[1]=a[1],len=1;
for(int i=1; i<=n; ++i) {
	if(a[i]>f[len])
		f[++len]=a[i];
	else {
		int pos=lower_bound(f+1,f+1+len,a[i])-f;
   		f[pos]=a[i];
	}
}