POJ 2533 Longest Ordered Subsequence

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <climits>
 7 #include <vector>
 8 #include <queue>
 9 #include <cstdlib>
10 #include <string>
11 #include <set>
12 #include <stack>
13 #define LL long long
14 #define pii pair<int,int>
15 #define INF 0x3f3f3f3f
16 using namespace std;
17 const int maxn = 1010;
18 int dp[maxn],d[maxn],n;
19 int main() {
20     while(~scanf("%d",&n)){
21         for(int i = 0; i < n; ++i){
22             scanf("%d",d+i);
23             dp[i] = INF;
24         }
25         dp[n] = INF;
26         for(int i = 0; i < n; ++i){
27             int *p = lower_bound(dp,dp+n+1,d[i]);
28             *p = d[i];
29         }
30         printf("%d\n",lower_bound(dp,dp+n+1,INF)-dp);
31     }
32     return 0;
33 }