Stock Exchange(最长上升子序列LIS)

ops2003

　　题目链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=87125#problem/E
　　题意：
　　多组案例，每组案例给出字符串的长度，及字符串，找出字符串中最长上升子序列的长度。
　　案例：
　　Sample Input
　　6
　　5 2 1 4 5 3
　　3
　　1 1 1
　　4
　　4 3 2 1
　　Sample Output
　　3
　　1
　　1　　
　　分析：
　　为避免超时，需要使用二分查找。判断当前数字时候大于前一数字，如果大于则把它放在数组后面否则通过2分法，判断它的大小应该放的位置。循环一遍之后，数组存下来的就是最长上升子序列。
　　源代码：



1 #include<cstdio>
2 #include<cstring>
3 int L,count;
4 long a[100010],b[100010];
5 void search(long z)
6 {
7     int l=1,r=count,mid;
8     while(l<=r)//二分查找
9     {
10         mid=(l+r)/2;
11         if(b[mid]==z) return;
12         else
13         {
14             if(b[mid]>z) r=mid-1;
15             else l=mid+1;
16         }
17     }
18     if(l==count+1)
19     {
20         count++;
21         b[count]=z;
22     }
23     else
24         b[l]=z;
25 }
26 int main()
27 {
28     int L,i;
29     while(scanf("%d",&L)!=EOF)
30     {
31         memset(b,0,sizeof(b));
32         for(i=1;i<=L;i++)//输入字符串
33             scanf("%lld",&a);
34         count=1;
35         b[1]=a[1];
36         for(i=2;i<=L;i++)//查找最长上升子序列
37             search(a);
38         printf("%d\n",count);
39     }
40     return 0;
41 }