fork download
copy 
  1. // Author: Ankush Khanna
  2. #include <iostream>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <cassert>
  6.  
  7. using namespace std;
  8.  
  9. inline int lis(int *a, int n) {
  10.     vector<int> ans;
  11.     for (int i = 0; i < n; i++) {
  12.         auto it = lower_bound(ans.begin(), ans.end(), a[i]);
  13.         if (it == ans.end()) {
  14.             ans.push_back(a[i]);
  15.         } else {
  16.             *it = a[i];
  17.         }
  18.     }
  19.     return (int) ans.size();
  20. }
  21.  
  22. int main() {
  23.     ios_base :: sync_with_stdio(false);
  24.     cin.tie(nullptr);
  25.     cout.tie(nullptr);
  26.     int tt, a[100000];
  27.     cin >> tt;
  28.     assert(tt >= 1 && tt <= 10);
  29.     while (tt--) {
  30.         int n;
  31.         cin >> n;
  32.         assert(n >= 1 && n <= 100000);
  33.         for (int i = 0; i < n; i++) {
  34.             cin >> a[i];
  35.             assert(a[i] >= 1 && a[i] <= 1000000000);
  36.         }
  37.         cout << lis(a, n) << '\n';
  38.     }
  39.     return 0;
  40. }
  41.  
Success #stdin #stdout 0s 15504KB
comments (?)
stdin
copy 
2
8
6 2 5 1 7 4 8 3
6
10 9 8 7 6 11
stdout
copy 
4
2
https://ideone.com/oyWSBZ
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!