约定：文章中的n表示单个字符串长度

LIS：最长上升子序列

有 \(O(n^2)\) 和 \(O(nlogn)\) 做法。

当然，\(O(n^2)\) 的做法经过优化可以达到 \(O(nlogn)\)。

\(O(n^2)\) 做法

设计dp状态：\(dp[i]\) 表示以i结尾的最长上升子序列。

有转移方程 \(\displaystyle dp[i]=\max_{j<i}dp[j]+1\)。

优点：实现简单，可以记录序列中到每个点的LIS。

缺点：时间负杂度高。

代码演示：

#include<bits/stdc++.h>
using namespace std;
inline void rd(int &x){
	int s=0,f=1; char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=0; c=getchar();}
	while(c>='0'&&c<='9'){s=s*10+c-48; c=getchar();}
	x=f? s:-s;
}
const int N=1e3+5;
int n, a[N], dp[N];
signed main(){
	rd(n);
	for(int i=1; i<=n; i++) rd(a[i]);
	for(int i=1; i<=n; i++){
		dp[i]=1;
		for(int j=i-1; ~j; j--){
			if(a[j]<a[i]) dp[i]=max(dp[i], dp[j]+1);
		}
	}
	int ans=0;
	for(int i=1; i<=n; i++) ans=max(ans, dp[i]);
	printf("%d\n", ans);
	return 0;
}

\(O(nlogn)\)做法

Solve 1

考虑优化 \(O(n^2)\) 的做法，将转移中的min用数据结构维护（如树状数组），可以达到 \(O(nlogn)\)。

这种做法保留了可以知道每个点LIS的特性，是优秀的LIS算法。

Solve 2

设计 \(f[]\) 数组。

\(f[i]\) 指当前的LIS中，第i个元素的最小值。

每加入序列中的一个数，如果大于当前LIS的最后一个数，

直接更新LIS，将当前数加入LIS末尾。

否则二分查找当前 \(f[]\) 中最靠后的一个比该数大（上一个小于等于它）的数，将其替换成它。

优点：时间复杂度低。

缺点：不够直观，且只能记录最终的LIS。

代码演示：

#include<bits/stdc++.h>
using namespace std;
inline void read(int &x){
	int s=0,f=1; char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=0; c=getchar();}
	while(c>='0'&&c<='9'){s=s*10+c-48; c=getchar();}
	x=f? s:-s;
}
const int N=1e3+10;
int n,a[N],dp[N];
signed main(){
	read(n);
	for(int i=1;i<=n;i++)
		read(a[i]), dp[i]=INT_MAX;
	dp[1]=a[1]; int len=1;
	for(int i=1;i<=n;i++){
		if(a[i]>dp[len]) dp[++len]=a[i];
		else{
			int l=0, r=len;
			while(l!=r-1){
				int mid=(l+r)/2;
				if(a[i]>dp[mid]) l=mid;
				else r=mid;
			}
			dp[r]=a[i];
		}
	}
	printf("%d",len);
	return 0;
}

例题：OpenJudge - 最长上升子序列

LCS：最长公共子序列

对于通常的LCS问题，仅有 \(O(n^2)\) 算法。下面是对其的介绍。

求解串 \(S\) 与串 \(T\) 的LCS，记 \(dp[i][j]\) 为考虑到 \(S\) 的前 \(i\) 位，\(T\) 的前 \(j\) 位，LCS的最长长度。

我们分类讨论。

若 \(S[i] \neq T[j]\)，则有转移：\(dp[i][j]=min(dp[i-1][j],dp[i][j-1])\)。
这很好理解，即 \(S[i]\) 和 \(T[j]\) 不会互相产生贡献，则当前状态肯定由丢弃其中一个转移过来。进一步说明，若 \(S[i]\) 同 \(T\) 的向前某一位配对，\(T[j]\) 则肯定无法在 \(S\) 中找到配对字符，因为 \(S[i]\) 是当前 \(S\) 的最后一位。反之也是这样。

若 \(S[i]=T[j]\)，则当前位相匹配肯定最优。因为若 \(S[i]\) 与 \(T\) 前面的字符匹配，则 \(T[j]\) 无法匹配，答案肯定不会更优。故转移为 \(dp[i][j]=dp[i-1][i-1]+1\)。