Stock Exchange（LIS最长上升子序列问题）

qq70191

　　题目链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=87125#problem/E
　　题意：
　　输入L，再输入长为L的序列，找出最长上升子序列的长度。注意选出的上升子序列中相邻元素不能相等。
　　案例：
　　input
　　6
　　5 2 1 4 5 3
　　3  
　　1 1 1
　　4
　　4 3 2 1
　　output
　　3
　　1
　　1
　　思路分析：
　　找出比前一个数大的数存入数组，如果小于放到前面，替换比它大一点的数，直到找出最长子序列，输出maxn。
　　源代码如下：



1 #include<iostream>
2 #include<cstdio>
3 #define MAX 100005
4 using namespace std;
5 int main()
6 {
7     int L,i,a,d[MAX],maxn;
8     while(scanf("%d",&L)!=EOF)
9     {
10         maxn=0;
11         d[0]=-1;
12         for(i=0;i<L;i++)
13         {
14             scanf("%d",&a);
15             if(a>d[maxn])
16                 d[++maxn]=a;            //储存
17             else
18             {
19                 int x=1,y=maxn,mid;
20                 while(x<=y)              //替换
21                 {
22                     mid=(x+y)>>1;
23                     if(a>d[mid])
24                         x=mid+1;
25                     else
26                         y=mid-1;
27                 }
28                 d[x]=a;
29             }
30         }
31         printf("%d\n",maxn);
32     }
33     return 0;
34 }