最长上升子序列

最长上升子序列（LCS) 模板
复杂度 o(nlog(n))

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
void Binary_Insert(int ar[],int &len,int x)
{
    if(x > ar[len-1])
    {
        ar[len] = x;
        len++;
        return ;
    }
    int l = 0,r = len-1;
    int mid;
    while(r >= l)
    {
         mid = l + ((r-l)>>1);
        if(ar[mid] > x)
            r = mid-1;
        else
            l = mid+1;
    }
    ar[l] = x;
}
template  <class It>
int n_lisLength(It begin,It end)
{
    typedef typename iterator_traits<It>::value_type T;
    T inf = 1<<30;
    vector<T> best(end-begin,inf);
    for(It i = begin; i != end; ++i)
       *lower_bound(best.begin(),best.end(),*i) = *i;
    return lower_bound(best.begin(),best.end(),inf) - best.begin();

}

int main () {

  cout<<(!!0)<<endl;
  int br[10] = {0,2,3,1,7,8,9,6,5,4};
  cout<<n_lisLength(br,br+10)<<endl;
  int ar[1000];
  int len = 1;
  for(int i = 0;i <= 10; ++i)
      ar[i] = 1000;
   ar[0] = br[0];
  for(int i = 1;i < 10; ++i)
     Binary_Insert(ar,len,br[i]);
  for(int i = 0;i < len; ++i)
     cout<<ar[i]<<" ";

  return 0;
}