LIS(最长递增子序列)

算法：动态规划＋二分查找
时间复杂度：O(nlogn)

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<map>
#include<cstdio>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'

using namespace std;
typedef long long ll;

const int maxn = 1e3+10;
int a[maxn];
int d[maxn];
int len;
int main() {
   
	int n;cin >> n;
	for (int i = 0;i < n;++i)cin >> a[i];
	d[0] = a[0];
	len = 1;
	for (int i = 1;i < n;++i) {
   
		if (a[i] > d[len - 1]) {
   
			d[len] = a[i];
			++len;
		}
		else {
   
			int pos = lower_bound(d, d + len, a[i]) - d;
			d[pos] = a[i];
		}
	}
	printf("%d", len);
	return 0;
}