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

题目链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=87125#problem/E

题意：

输入L，再输入长为L的序列，找出最长上升子序列的长度。注意选出的上升子序列中相邻元素不能相等。

案例：

input

5 2 1 4 5 3

1 1 1

4 3 2 1

output

思路分析：

找出比前一个数大的数存入数组，如果小于放到前面，替换比它大一点的数，直到找出最长子序列，输出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
",maxn);
32     }
33     return 0;
34 }