SHARE
TWEET

Untitled

a guest Apr 23rd, 2019 55 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;  
  4.  
  5. int CeilIndex(std::vector<int>& v, int l, int r, int key)
  6. {
  7.     while (r - l > 1) {
  8.         int m = l + (r - l) / 2;
  9.         if (v[m] >= key)
  10.             r = m;
  11.         else
  12.             l = m;
  13.     }
  14.  
  15.     return r;
  16. }
  17.  
  18. int LongestIncreasingSubsequenceLength(std::vector<int>& v)
  19. {
  20.     if (v.size() == 0)
  21.         return 0;
  22.  
  23.     std::vector<int> tail(v.size(), 0);
  24.     int length = 1;
  25.  
  26.     tail[0] = v[0];
  27.     for (size_t i = 1; i < v.size(); i++) {
  28.  
  29.         if (v[i] < tail[0])
  30.             tail[0] = v[i];
  31.  
  32.         else if (v[i] > tail[length - 1])
  33.             tail[length++] = v[i];
  34.         else
  35.             tail[CeilIndex(tail, -1, length - 1, v[i])] = v[i];
  36.     }
  37.  
  38.     return v.size()-length;
  39. }
  40.  
  41. int main()
  42. {
  43.     int a,n,b;
  44.     vector<int> v;
  45.     cin>>a;
  46.     for(int i=0;i<a;i++)
  47.     {
  48.         cin>>n;
  49.         for(int j=0;j<n;j++)
  50.         {
  51.             cin>>b;
  52.             v.push_back(b);
  53.         }
  54.         cout<<LongestIncreasingSubsequenceLength(v)<<endl;
  55.         v.clear();
  56.     }
  57. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top