Dãy con tăng dài nhất bản khó (O(NlogN))

Tương tự như version1 của nó chỉ khác nhau chỗ tìm j<i sao cho f[j] lớn nhất mà a[j]<a[i] thôi. Ở đây ta áp dụng tìm kiếm nhị phân trong việc tìm kiếm j. Do đó thuật toán có độ phức tạp O(NlogN).
Solution C++:

#include <vector>
using namespace std;
 
/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */
void find_lis(vector<int> &a, vector<int> &b)
{
 vector<int> p(a.size());
 int u, v;
 
 if (a.empty()) return;
 
 b.push_back(0);
 
 for (size_t i = 1; i < a.size(); i++) 
        {
                // If next element a[i] is greater than last element of current longest subsequence a[b.back()], just push it at back of "b" and continue
  if (a[b.back()] < a[i]) 
                {
   p[i] = b.back();
   b.push_back(i);
   continue;
  }
 
                // Binary search to find the smallest element referenced by b which is just bigger than a[i]
                // Note : Binary search is performed on b (and not a). Size of b is always <=k and hence contributes O(log k) to complexity.    
  for (u = 0, v = b.size()-1; u < v;) 
                {
   int c = (u + v) / 2;
   if (a[b[c]] < a[i]) u=c+1; else v=c;
  }
 
                // Update b if new value is smaller then previously referenced value 
  if (a[i] < a[b[u]]) 
                {
   if (u > 0) p[i] = b[u-1];
   b[u] = i;
  } 
 }
 
 for (u = b.size(), v = b.back(); u--; v = p[v]) b[u] = v;
}
 
/* Example of usage: */
#include <cstdio>
int main()
{
 int a[] = { 1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 };
 vector<int> seq(a, a+sizeof(a)/sizeof(a[0])); // seq : Input Vector
 vector<int> lis;                              // lis : Vector containing indexes of longest subsequence 
        find_lis(seq, lis);
 
        //Printing actual output 
 for (size_t i = 0; i < lis.size(); i++)
  printf("%d ", seq[lis[i]]);
        printf("\n");    
 
 return 0;
}

Hay:

#define index_of(as,x) distance(as.begin(),lower_bound(as.begin(),as.end(),x))

#define inf 99999999

vector<int> lis_fast(const vector<int>& a){

            const int n=a.size();

            vector<int> A(n,inf);

            vector<int> id(n);

            for(int i=0;i<n;i++){

                        id[i]=index_of(A,a[i]);

                        //cout << id[i] << endl; system("pause");

                        A[ id[i] ]=a[i];

            }

            int m=*max_element(id.begin(),id.end());

            vector<int> b(m+1);

            for(int i=n-1;i>-1;i--)

                if(id[i]==m) b[m--]=a[i];

            return b;

}

Tham khảo: http://en.wikipedia.org/wiki/Longest_increasing_subsequence
http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence