fork download 
  1. //LIS no recursive
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. //#define LOCAL
  5. #define cls ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
  6. #define Mod 998244353
  7. #define ll long long int
  8. #define sf scanf
  9. #define pf printf
  10. #define rep(i,a,b) for(int i=a;i<b;i++)
  11. #define dec(i,a,b) for(int i=b;i>=a;i--)
  12. #define mset(a,b) memset(a,b,sizeof(a))
  13. const int maxn=2333;
  14. int a[maxn];
  15. int LIS(int a[],int n){
  16.     int lis[n];
  17.     lis[0]=1;
  18.     for(int i=1;i<n;i++){
  19.         lis[i]=1;
  20.         for(int j=0;j<i;j++){
  21.             if(a[i]>a[j]&&lis[i]<lis[j]+1){
  22.                 lis[i]=lis[j]+1;
  23.             }
  24.         }
  25.     }
  26.     return *max_element(lis,lis+n);
  27. }
  28. int main() {
  29. #ifdef LOCAL
  30.     freopen("in.in","r",stdin);
  31. #endif // LOCAL
  32.     cls;
  33.     int n;
  34.     cin>>n;
  35.     for(int i=0;i<n;i++){
  36.         cin>>a[i];
  37.     }
  38.     cout<<LIS(a,n)<<endl;
  39. 	return 0;
  40. }
  41.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin 
3
2 1 3
stdout 
2
https://ideone.com/HygUhu
language:
C++14 (clang 8.0)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!