https://vjudge.net/problem/POJ-2533#author=karl_sc
poj天天炸 放个VJ页面吧(逃

很经典的LIS（ longest  increasing subsequence ）
说实话今天学习真的没有状态 可能是有点疲惫了？。。。
刚开始深入的学dp 那这个经典问题好好的谈一谈

我们知道dp的经典思维就是看上一个的状态 因此 最长上升子序列也就是
n的最长上升子序列也就是n-1的最长上升子序列 我也不知道我说了一句什么话 还是列公式吧
lis[i]=max(lis[j])+1(arr[j]<arr[i]) 就是说 每找到一个数 就遍历所有的数字 找到比他小且lis最大的那个数字 然后 就是那个数的lis+1
举个例子：
1 7 3 5 9 4 8
lis[1]=1;
lis[2]=1+1=2;
lis[3]=1;
lis[4]=lis[1]+1=2;
lis[5]=lis[4]+1=3;
lis[6]=lis[3]+1=2;
lis[7]=lis[3]+1=2;
lis[8]=lis[5]+1=4;
lis[9]=lis[8]+1=5;
代码很简单 但是今天很迷的状态还是写错了不少地方 好菜
分析下时间复杂度 每一个数都要便利前面所有的数字 O（n^2）无疑了

#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<ctime>
#include<map>
#include<stack>
#include<set>
#include<cstring>
#include<sstream>
using namespace std;
typedef long long ll;
const int maxn = 1005;
int lis[maxn];
int arr[maxn];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	lis[0] = 1;
	int maxn = 0;
	for (int i = 1; i < n; i++) {
		maxn = 0;
		for (int j = 0; j < i; j++) {
			if (arr[i] > arr[j]) {
				maxn = max(maxn, lis[j]);
			}
		}
		lis[i] = maxn+1;
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		ans = max(ans, lis[i]);
	}
	cout << ans << endl;
	return 0;
}

好 那么我们知道 n2的复杂度是有点丑的
我们可以把他优化为nlogn的复杂度
来 讲讲我们下一种想法
还是那个例子 1 7 3 5 9 4 8
我们搞一个数组B
扫一遍数组
1 入 B:1
7 入 B: 1 7
3 入 B: 1 3
5 入 B: 1 3 5
9 入 B: 1 3 5 9
4 入 B: 1 3 4
8 入 B: 1 3 4 8
你看 这样B 是不是就是我们要的数组啦 但是有个疑问 这不还是扫了两边吗
等等 这个时候 我们的二分查找就来了 查找的时候用二分 n变logn
妈的心态炸了 写了这么久的Lower_bound 都是wa 找了个大佬的直接贴一下
来自：https://blog.csdn.net/aqa2037299560/article/details/82873340

#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<ctime>
#include<map>
#include<stack>
#include<set>
#include<cstring>
#include<sstream>
using namespace std;
typedef long long ll;
int i, j, n, s, t, a[100001];
int main()
{
	cin >> n;
	a[0] = -1000000;
	for (i = 0; i < n; i++)
	{
		cin >> t;
		if (t > a[s]) a[++s] = t;
		else
		{
			int l = 1, h = s, m;
			while (l <= h)
			{
				m = (l + h) / 2;
				if (t > a[m]) l = m + 1;
				else h = m - 1;
			}
			a[l] = t;
		}
	}
	cout << s << endl;
}

还有一种树状数组的做法 这里不谈了
https://blog.csdn.net/George__Yu/article/details/75896330