Longest Ordered Subsequence

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 using namespace std;
 5 #define max 1000
 6 int s[max+10];
 7 int max1[max+10];
 8 int main()
 9 {
10     int n,m;
11     cin>>n;
12     for(int i=1;i<=n;i++)
13     {
14         cin>>s[i];
15     }
16     max1[1]=1;
17     for(int i=2;i<=n;i++)
18     {
19         m=0;
20         for(int j=1;j<i;j++)
21         {
22             if(s[i]>s[j])
23             {
24                 if(m<max1[j])
25                 {
26                     m=max1[j];
27                 }
28             }
29         }
30         max1[i]=m+1;
31     }
32     int max2=-1;
33     for(int i=1;i<=n;i++)
34     {
35         if(max2<max1[i])
36         {
37             max2=max1[i];
38         }
39     }
40     cout<<max2<<'
';
41     return 0;
42 }
View Code