最长上升子序列（LIS，Longest Increasing Subsequence）
“给定n个整数 A1， A2，… ，An，按从左到右的顺序选出尽量多的整数，组成一个上升子序列（子序列可以理解为：删除0个或多个数，其他数的顺序不变）。例如序列1，6，2，3，7，5，可以选出上升子序列1，2，3，5，也可以选出1，6，7，但前者更长。选出的上升子序列相邻元素不能相等”——《算法竞赛入门经典》
（部分解法灵感来源于洛谷题解）
解法（动态规划）
状态转移方程
时间复杂度
代码
1
2
3
4
5
6
7
8
9
10
| int LIS(){
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 ans=-1;
for(int i=1;i<=n;i++) ans=max(ans, dp[i]);
return ans;
}
|
树状数组优化
思路
动态规划的状态转移方程$d(i)=max{0, d(j)|j<i, A[j]<A[i]}$在计算第$i$个元素是需要访问第$1$至$i$个元素，使时间复杂度为$O(n^2)$。我们用树状数组优化这一步骤，就可以使时间复杂度降低。
时间复杂度
具体操作
创建树状数组C，以A[i]$_{i\in[1,n]}$为C的下标，代表以A[i]为末尾的最长上升子序列的长度。
从1至n遍历A的元素，对于元素A[i]，用qry1X()求出以从1至A[i]为末尾的最长上升子序列的长度的最大值，对A[i]和大于A[i]的值更新为k=qry1X()+1（树状数组操作）。
k的最大值即为最长上升子序列的长度。
代码
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
| int lowbit(int x) {return x&(-x);}
int qry1X(int x){
int ans=-1;
for(int i=x;i>0;i-=lowbit(i)){
ans=max(ans, C[i]);
}
return ans;
}
void chgXoo(int x, int k){
for(int i=x;i<=biggest;i+=lowbit(i)){
C[i]=max(C[i], k);
}
}
int d(){
memset(C, 0, sizeof(C));
int ans=-1;
for(int i=1;i<=cnt;i++){
int maxn=qry1X(A[i]);
chgXoo(A[i]+1, ++maxn);
ans=max(ans, maxn);
}
return ans;
}
|
其他子序列问题
最长不上升子序列
解法（动态规划）
状态转移方程
时间复杂度和LIS相同
代码
1
2
3
4
5
6
7
8
9
10
| int d(){
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++){
if(A[j]>=A[i]) dp1[i]=max(dp[i], dp[j])+1;
}
}
int ans=-1;
for(int i=1;i<=n;i++) ans=max(ans, dp[i]);
return ans;
}
|
树状数组优化
代码
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
| int lowbit(int x) {return x&(-x);}
int qryXoo(int x){
int ans=-1;
for(int i=x;i<=biggest;i+=lowbit(i)){
ans=max(ans, C[i]);
}
return ans;
}
void chg1X(int x, int k){
for(int i=x;i>0;i-=lowbit(i)){
C[i]=max(C[i], k);
}
}
int d(){
memset(C, 0, sizeof(C));
int ans=-1;
for(int i=1;i<=cnt;i++){
int maxn=qryXoo(A[i]);
chg1X(A[i], ++maxn);
ans=max(ans, maxn);
}
return ans;
}
|
最长公共子序列（LCS，Longest Common Subsequence）
解法（动态规划）
状态转移方程
时间复杂度
代码
1
2
3
4
5
6
7
8
9
| int d(){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dp[i][j]=max(dp[i-1][j], dp[i][j-1]);
if(P[i]==Q[j]) dp[i][j]=max(dp[i][j], dp[i-1][j-1]+1);
}
}
return dp[n][m];
}
|
树状数组优化（特定情况下可使用）
思路
引用自洛谷阮行止大佬的博客，原文中LIS和LCS有轻微混淆，提出如下修正
关于为什么可以转化成LIS问题，这里提供一个解释。
A: 3 2 1 4 5
B: 1 2 3 4 5
我们不妨给它们重新标个号：把3标成a,把2标成b，把1标成c……于是变成：
A: a b c d e
B: c b a d e
这样标号之后，LCS长度显然不会改变。但是出现了一个性质：
两个序列的子序列，一定是A的子序列。而A本身就是单调递增的。
因此这个子序列是单调递增的。
换句话说，只要这个子序列在B中单调递增，它就是A的子序列。
哪个最长呢？当然是B的LIS最长。
自此完成转化。
具体操作
按照P数组的数据对Q数组进行类似于离散化的操作
对Q数组求LIS
代码
洛谷P1439 【模板】最长公共子序列
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
| int lowbit(int x){
return x&(-x);
}
int qry1X(int x){
int ans=-1;
for(int i=x;i>0;i-=lowbit(i)) ans=max(ans, C[i]);
return ans;
}
void chgXoo(int x, int k){
for(int i=x;i<=n;i+=lowbit(i)) C[i]=max(C[i], k);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>P[i];
T[P[i]]=i;
}
for(int i=1;i<=n;i++){
int temp;
cin>>temp;
Q[i]=T[temp];
}
int ans=-1;
for(int i=1;i<=n;i++){
int maxn=qry1X(Q[i]);
chgXoo(Q[i], ++maxn);
ans=max(ans, maxn);
}
cout<<ans;
return 0;
}
|
总结
最长（非）上升/下降子序列问题
解法（动态规划）
最长上升（非下降）子序列
最长下降（非上升）子序列
树状数组优化
最长上升（非下降）子序列：搜索比A[i]小的数，更新大于（大于等于）A[i]的数
最长下降（非上升）子序列：搜索比A[i]大的数，更新小于（小于等于）A[i]的数
树状数组代码：
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
| int lowbit(int x) {return x&(-x);}
void chg1X(int x, int k){
for(int i=x;i>0;i-=lowbit(i)){
C[i]=max(C[i], k);
}
}
int qry1X(int x){
int ans=-1;
for(int i=x;i>0;i-=lowbit(i)){
ans=max(ans, C[i]);
}
return ans;
}
void chgXoo(int x, int k){
for(int i=x;i<=biggest;i+=lowbit(i)){
C[i]=max(C[i], k);
}
}
int qryXoo(int x){
int ans=-1;
for(int i=x;i<=biggest;i+=lowbit(i)){
ans=max(ans, C[i]);
}
return ans;
}
|