fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const long long MaxN = 2e5 + 5;
  4.  
  5. long long n, a[MaxN], d[MaxN];
  6.  
  7. int main()
  8. {
  9.     ios_base::sync_with_stdio(0);
  10.     cin.tie(0);
  11.  
  12.     cin >> n;
  13.     for(long long i = 1; i <= n; i++)
  14.         cin >> a[i];
  15.  
  16.     d[0] = LLONG_MIN;
  17.     for(long long i = 1; i <= n; i++)
  18.         d[i] = LLONG_MAX;
  19.  
  20.     long long ans = 0;
  21.  
  22.     for(long long i = 1; i <= n; i++)
  23.     {
  24.         long long pos = lower_bound(d + 1, d + ans + 2, a[i]) - d;
  25.         d[pos] = a[i];
  26.         ans = max(ans, pos);
  27.     }
  28.  
  29.     cout << ans;
  30. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/OKnBLa
language:
C++14 (gcc 8.3)
created:
9 hours 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!