最长上升子序列LIS

 1 #include<iostream>
 2 #include<cstdio>
 3 #define maxn 30
 4 using namespace std;
 5 template<typename T>
 6 inline void read(T &x){
 7     x=0; bool flag=0; char c=getchar();
 8     for(;!isdigit(c);c=getchar()) if(c==‘-‘) flag=1;
 9     for(;isdigit(c);c=getchar()) x=x*10+(c^48);
10     if(flag) x=-x;
11 }
12 
13 int n,f[maxn],a[maxn];
14 int ans=0;
15 
16 void LIS(){
17     for(int i=1;i<=n;i++){
18         f[i]=1;
19         for(int j=1;j<i;j++)
20             if(a[j]<a[i])
21                 f[i]=max(f[i],f[j]+1);
22     }
23     for(int i=1;i<=n;i++)
24         ans=max(ans,f[i]);
25 }
26 
27 
28 int main(){
29     read(n);
30     for(int i=1;i<=n;i++) read(a[i]);
31     LIS();
32     cout<<ans<<endl;
33     return 0;
34 }