SHARE
TWEET

Longest Increasing Subsequence

keverman Feb 27th, 2018 43 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. int pos(std::vector<int> &tail, unsigned int lhs, unsigned int rhs, int key)
  2. {
  3.     while(rhs - 1 > lhs)
  4.     {
  5.         int mid = lhs + (rhs - lhs) / 2;
  6.         tail[mid] > key ? rhs = mid : lhs = mid;
  7.     }
  8.  
  9.     if(rhs == tail.size() - 1)
  10.         tail.push_back(INF);
  11.  
  12.     return rhs;
  13. }
  14.  
  15. int LISLen(std::vector<int> &seq)
  16. {
  17.     std::vector<int> tail(3);
  18.     tail[0] = -INF, tail[1] = seq[0], tail[2] = INF;
  19.  
  20.     for(unsigned int i = 1; i < seq.size(); i++)
  21.         tail[pos(tail, tail.size(), seq[i])] = seq[i];
  22.  
  23.     return tail.size() - 2;
  24. }
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top