Stock Exchange（LIS最长上升子序列问题）
题目链接：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,maxn;
8 while(scanf("%d",&L)!=EOF)
9 {
10 maxn=0;
11 d=-1;
12 for(i=0;i<L;i++)
13 {
14 scanf("%d",&a);
15 if(a>d)
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)
24 x=mid+1;
25 else
26 y=mid-1;
27 }
28 d=a;
29 }
30 }
31 printf("%d\n",maxn);
32 }
33 return 0;
34 }
页:
[1]