Stock Exchange(最长上升子序列LIS)
题目链接：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,b;
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==z) return;
12 else
13 {
14 if(b>z) r=mid-1;
15 else l=mid+1;
16 }
17 }
18 if(l==count+1)
19 {
20 count++;
21 b=z;
22 }
23 else
24 b=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=a;
36 for(i=2;i<=L;i++)//查找最长上升子序列
37 search(a);
38 printf("%d\n",count);
39 }
40 return 0;
41 }
页:
[1]