fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<int> LIS(vector<int>& a) {
  5.     vector<int> tail(a.size(), 0);
  6.     int length = 1;
  7.  
  8.     tail[0] = a[0];
  9.     for (size_t i = 1; i < a.size(); i++) {
  10.         if (a[i] < tail[0])
  11.             tail[0] = a[i];
  12.         else if (a[i] > tail[length - 1])
  13.             tail[length++] = a[i];
  14.         else
  15.             tail[lower_bound(tail.begin(), tail.begin() + length, a[i]) - tail.begin()] = a[i];
  16.     }
  17.  
  18.     return vector<int>(tail.begin(), tail.begin() + length);
  19. }
  20.  
  21. int main() {
  22.     vector<int> a = {1, 2, 3, 1, 2, 3};
  23.     vector<int> b = {2, 1, 3, 3, 2, 1};
  24.  
  25.     map<int, int> indices;
  26.     for (int i = 0; i < a.size(); i++)
  27.         indices[a[i]] = i + 1;
  28.  
  29.     for (int& x : b)
  30.         x = indices[x];
  31.  
  32.     vector<int> lis = LIS(b);
  33.     cout << "Length of LIS is " << lis.size() << "\n";
  34.     for (int x : lis)
  35.         cout << x << " ";
  36.     cout << "\n";
  37.  
  38.     return 0;
  39. }
  40.  
Success #stdin #stdout 0s 5296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Length of LIS is 2
4 5
https://ideone.com/nvDIee
language:
C++14 (gcc 8.3)
created:
1 year 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!