|
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
35
36
37
38
39
40
41
42
43
44
45
46
47 |
#include "stdafx.h"#include<iostream>#include<cstdio>#include<cstring>using
namespace std;long
long d[100000],a[100000];long
long len,i,k,n;long
long min(long
long t){ long
long s,w,mid; s=0; w=len; while(s<w) { mid=(s+w)/2; if(d[mid]<=t) s=mid+1; else w=mid; } return
s;}int
_tmain(int
argc, _TCHAR* argv[]){ cin>>n; for(i=1;i<=n;i++) cin>>a[i]; len=0; d[0]=-29888888;//设一个非常小的数字 for(i=1;i<=n;i++) { if(a[i]>=d[len]) { len++; d[len]=a[i]; cout<<d[len]<<" "; }//放置数组 else { k=min(a[i]); d[k]=a[i]; } } cout<<endl; cout<<len<<endl; return
0;} |
注意：这个算法可以获得最长序列的长度值，但是数组d中保存的并不是最长长度的元素。
原文：http://www.cnblogs.com/plmmlp09/p/3713928.html