最长递减子序列(nlogn):
1 int find(int n,int key)
2 {
3 int left=0;
4 int right=n;
5 while(left<=right)
6 {
7 int mid=(left+right)/2;
8 if(res[mid]>key)
9 {
10 left=mid+1;
11 }
12 else
13 {
14 right=mid-1;
15 }
16 }
17 return left;
18 }
19
20 int Lis(int a[],int n)
21 {
22 int r=0;
23 res[r]=a[0];
24 r++;
25 for(int i=1;i<n;i++)
26 {
27 if(res[r-1]>a[i])
28 {
29 res[r]=a[i];
30 r++;
31 }
32 else
33 {
34 int loc=find(r,a[i]);
35 res[loc]=a[i];
36 }
37 }
38 return r;
39 }