最长上升子序列LIS模板

参考链接：https://blog.csdn.net/lxt_Lucia/article/details/81206439

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<string>
#include<string.h>
#include<iomanip>
#include<stdlib.h>
#include<map>
#include<queue>
#include<limits.h>
#include<climits>
#include<fstream>
#include<stack>
typedef unsigned long long ll;
using namespace std;


const int N = 5e3 + 10;
int n;
ll mp[N], v[N];
int binsearch(int l, int r, ll val)
//二分查找替换，不改变最大长度，因为如果当前长度小，那么长度沿用以前的最大长度
//如果当前数大，那么接到任何一个长度后面，就相当于默认取了最长的子序列
{
	int ll = l, rr = r, mid ;
	while (ll < rr)
	{
		mid = ll + (rr - ll) / 2;
		if (v[mid] < val)
		{
			ll = mid + 1;
		}
		else rr = mid;
	}
	return ll;
}
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++) { cin >> mp[i]; v[i] = LLONG_MAX; }
	v[1] = mp[1];
	int ans = 1;
	for (int i = 2; i <= n; i++)
	{
		if (mp[i] > v[ans])
		{
			ans++;
			v[ans] = mp[i];
		}
		else
			v[binsearch(1, ans, mp[i])] = mp[i];
	}
	cout << ans;
	return 0;
}