Stock Exchange (最大上升子子串)

 1 /*
 2 题意：
 3 给定L个整数A1,A2，...，An，按照从左到右的顺序选出尽量多的整数，
 4 组成一个上升序列（子序列可以理解为：删除0个或者多个数，其他的数的吮吸不变）。
 5 例如，1，6，2，3，7，5，可以选出上升子序列1，2，3，5，也可以选出1，6，7，
 6 但前者更长，选出的上升子序列中相邻元素不能相等。
 7 思路：
 8 开辟一个栈，每次取栈顶元素s和读到的元素a做比较，如果a>s，  则加入栈；
 9 如果a<s，则二分查找栈中的比a大的第1个数，并替换。  最后序列长度为栈的长度。
10 */
11 #include<iostream>
12 #include<algorithm>
13 #include<cstring>
14 using namespace std;
15 
16 int a[100010];
17 
18 int main()
19 {
20     int n,u,k;
21     while(cin>>n)
22     {
23         a[0]=-1;
24         k=0;
25         for(int i=0;i<n;i++)
26         {
27             cin>>u;
28             if(a[k]<u)
29             {
30                 a[++k]=u;
31             }
32             else
33             {
34                 int l=1,r=k,mid;
35                 while(l<=r)
36                 {
37                     mid=l+(r-l)/2;
38                     if(u>a[mid])
39                         l=mid+1;
40                     else
41                         r=mid-1;
42                 }
43                 a[l]=u;
44             }
45         }
46         cout<<k<<endl;
47     }
48 }

 1 #include <stdio.h>
 2 #include <string.h>
 3 //author:YangSir
 4 int a[100005];
 5 int main(){
 6     int n,i,max,b,num,x;
 7     while(~scanf("%d",&n)){
 8         num=1;
 9         a[0]=-5456456;
10         scanf("%d",&b);
11         a[1]=max=b;
12         for(i=1;i<n;i++){
13             scanf("%d",&b);//数组的每个值变化的过程就表示子串一个个代入
14             if(max<b){
15                 max=b;
16                 num++;
17                 a[num]=max;//子串在增长
18             }
19             else{
20                 x=num-1;
21                 while(a[x]>=b)
22                     x--;
23                 a[x+1]=b;
24             }
25             max=a[num];//max可能会变
26         }
27         printf("%d
",num);
28     }
29     return 0;
30 }

 1 #include<stdio.h>
 2 #include<algorithm>
 3 using namespace std;
 4 #define INF 1<<30
 5 int main()
 6 {
 7     int n, a[100010], dp[100010];
 8 
 9     while(~scanf("%d", &n))
10     {
11         for(int i=0; i<n; i++)
12         {
13             scanf("%d", a+i);
14             dp[i] = INF;
15         }
16         for(int i=0; i<n; i++)
17             *lower_bound(dp, dp+n, a[i]) = a[i];
18         printf("%d
", lower_bound(dp, dp+n, INF)-dp);
19     }
20     return 0;
21 }