题目链接在这里插入图片描述
题目要求两个串的最长公共子序列（LCS）

LIS（最长上升子序列）

最长子序列可以采用动态规划的方法求解。
定义：A为一个序列，现在求他的最长上升子序列

（1）$O(N^2)$算法

定义：dp[i]为以A[i]结尾的子序列的LIS的长度
初始化：$dp[i]=1,0\leq i<|A|$(每个字符本身都可以作为字串，长度为1)
转移方程：$dp[i]=max(dp[i],dp[j])$，其中，$j$满足：$0\leq j < i$并且$A[i]>A[j]$
结果=$max(dp[i]),0\leq i< |A|$

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
#include<iostream>
using namespace std;
int Array[100001],DP[100001];
int main(){
	int n;
	cin>>n;
	for(int i=0;i<0;++i){
		cin>>Array[i];
		DP[i]=1;
	}
	for(int i=0;i<n;++i){
		for(int j=0;j<i;++j){
			if(a[i]>a[j]){
				DP[i]=max(DP[i],DP[j]+1);
			}
		}
	}
	int ans=0;
	for(int i=0;i<n;++i){
		ans=max(DP[i],ans);
	}
	cout<<ans;
}


（2） $O(NlogN)$算法

开一个数组B

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 <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100001, INF = 0x7f7f7f7f;
int low[maxn], a[maxn];
int n, ans;
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		low[i] = INF;   //由于low中存的是最小值，所以low初始化为INF
	}
	low[1] = a[1];
	ans = 1;   //初始时LIS长度为1 
	for (int i = 2; i <= n; i++)
	{
		if (a[i] > low[ans])    //若a[i]>=low[ans]，直接把a[i]接到后面 
			low[++ans] = a[i];
		else       //否则，找到low中第一个>=a[i]的位置low[j]，用a[i]更新low[j] 
			*lower_bound(low, low + n, a[i]) = a[i];
	}
	printf("%d\n", ans);   //输出答案 
	return 0;
}