fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define ll long long
  5. const ll maxn=1e5+5;
  6. ll n,res;
  7. ll a[maxn];
  8. vector<ll>b(maxn,2e9);
  9. int main()
  10. {
  11.     ios_base::sync_with_stdio(0);
  12.     cin.tie(0);
  13.     cout.tie(0);
  14.    cin>>n;
  15.    for(ll i=1;i<=n;i++)
  16.    {
  17.        cin>>a[i];
  18.    }
  19.    b[0]=-2e9;
  20.    for(ll i=1;i<=n;i++)
  21.    {
  22.        ll l=lower_bound(b.begin(),b.end(),a[i])-b.begin();
  23.        b[l]=a[i];
  24.        res=max(res,l);
  25.    }
  26.    cout<<res;
  27. }
  28.  
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
8
1
2
3
2
9
4
5
6
stdout
copy 
6
https://ideone.com/eze5oe
language:
C++14 (gcc 8.3)
created:
237 days 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!