最长上升子序列模板与优化后的模板

未优化

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+10;

int n, ans;
int a[N], f[N];

int main()
{
	cin >> n;
	for (int i = 1;i <= n;i ++) {
		cin >> a[i];
		f[i] = 1;
		for (int j = 1;j < i;j ++)
			if (a[i] > a[j])
				f[i] = max (f[i], f[j] + 1);
		ans = max (ans, f[i]);
	}	
	
	cout << ans << endl;

	return 0;
}

优化后

优化原理

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+10;

int len = 0, n;
int a[N], d[N];

int binary_search (int x) { // 等价于 return lower_bound (d+1, d+1+len, x) - d
	int m, l = 1, r = len;
	while (l < r) {
		m = l + r >> 1;
		if (d[m] >= x) r = m;
		else l = m + 1; 
	}
	return l;
}

int main()
{
	cin >> n;
	for (int i = 1;i <= n;i ++) {
		cin >> a[i];
		if (a[i] > d[len]) d[++len] = a[i];
		else d[binary_search (a[i])] = a[i];
	}	
	
	cout << len << endl;
	
	return 0;
}