LIS(模板)

记录一下，O(nlgn)的算法求LIS
 1 //HHH
 2 #include <iostream>
 3 #include <stdio.h>
 4 #include <string.h>
 5 using namespace std;
 6 #define MX 1005
 7 
 8 int num[MX];
 9 int dp[MX];
10 int high[MX]; // 长为i的最小大小
11 
12 int bi_search(int x,int h)
13 {
14     int l=1,r=h;
15     int res=0;
16     while (l<=r)
17     {
18         int mid = (l+r)/2;
19         if (x>high[mid])    //不减序列改为 x>=high[mid]
20         {
21             res=mid;
22             l=mid+1;
23         }
24         else r=mid-1;
25     }
26     return res+1;
27 }
28 
29 int calc(int l,int r)
30 {
31     if (l>r) return 0;
32     memset(high,0,sizeof(high)); //要为最界限值
33     int h=1;
34     dp[l]=1;
35     high[1]=num[l];
36     for (int i=l+1;i<=r;i++)
37     {
38         if (num[i]>high[h]) //不减序列改为 x>=high[mid]
39         {
40             h++;
41             dp[i]=h;
42             high[h]=num[i];
43         }
44         else
45         {
46             int p=bi_search(num[i],h);
47             dp[i]=p;
48             high[p]=num[i];
49         }
50     }
51     return h;
52 }
53 
54 int main()
55 {
56     int n;
57     while (scanf("%d",&n)!=EOF)
58     {
59         for(int i=1;i<=n;i++)
60             scanf("%d",&num[i]);
61         printf("%d
",calc(1,n));
62     }
63     return 0;
64 }
View Code