最长公共上升子序列

link

#include 

using namespace std;

const int N = 3e3 + 10;

int a[N], b[N];
int dp[N][N]; // 以b[j]结尾的a[1] ~ a[i], b[1] ~ b[j], 的最长上升子序列

int main()
{
	int n;
	cin >> n;
	int ans = 0;
	for(int i = 1; i <= n; i ++) cin >> a[i];
	for(int i = 1; i <= n; i ++) cin >> b[i];
	for(int i = 1; i <= n; i ++)
	{
		int maxx = 0;// 1 ~ i, 与 1 ~ j中 最大数小于a[i]的最长上升公共子序列
		for(int j = 1; j <= n; j ++)
		{
			dp[i][j] = dp[i - 1][j];
			if(a[i] == b[j]) dp[i][j] = max(maxx + 1, dp[i][j]);
			if(a[i] > b[j]) maxx = max(dp[i][j], maxx);
			ans = max(ans, dp[i][j]);
		}
	}
	cout << ans << endl;
	return 0;
}

最长上升子序列

#include 

using namespace std;

const int N = 1e5 + 10;

int a[N];
int n;

int main()
{
	cin >> n;
	for(int i = 1; i <= n; i ++) cin >> a[i];
	vector v;
	v.push_back(a[1]);
	for(int i = 2; i <= n; i ++)
	{
		if(a[i] > v.back()) v.push_back(a[i]);
		else *lower_bound(v.begin(), v.end(), a[i]) = a[i]; // 用栈维护了每个长度的最小结尾的数字 
	} 
	cout << v.size() << endl;
	return 0;
}