最长上升子序列&&low_bound

发表于

复杂度nlogn;
这里主要是贪心的思想；
既然要求最长上升子序列那么，就要保证，第i（i > 0)个数他是的比他前一个数大的最小的一个数
就有个数组存储当前的最长序列及他的值。
当第i个数比这个个数组最后一个元素大的时候，那么此序列就添加一个数，反之，就在当前数列找一个刚好比他的的数来，然后替代他，
这里是最关键的一步这里就不停的更新，他的最小值。然偶这里用的是二分查找。这里可以使用low_bound函数，他是查找当前最小的比num这个数大的数，然后返回地址不存在则返回end，upper_bound则反之

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<algorithm>
using namespace std;

int v[1100000],f[1100000];

void me(int a)
{
	int i = 0;
	for(i;i < a;i++) v[i] = 0,f[i] = 0;
}

int main(){
	int n ;
	ios::sync_with_stdio(false);
	while(cin >> n)
	{
		int i = 0;
		while(i < n) cin>>v[i++];
		f[0] = v[0];
		int len = 0;
		for(i = 1;i < n;i++)
		{
			if(v[i] > f[len]) f[++len] = v[i];
			else{
				int j = lower_bound(f,f+len,v[i]) - f;
				f[j] = v[i];
			}
		}
		cout<<++len<<endl;
	    me(n);
	}
	return 0;
}