LIS - O(nlogn)

Code:


#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;
#define OO 1000000000
#define REP(i,start,end,step) for(int i = start; i < end; i += step)
#define DOWN(i,start,end,step) for(int i = start; i > end; i -= step)
#define index_of(as,x) distance(as.begin(),lower_bound(as.begin(),as.end(),x))

vector<int> lis_fast(const vector<int>& a)
{
const int n = a.size();
vector<int> A(n,OO);
vector<int> id(n);

REP(i,0,n,1)
{
id[i] = index_of(A,a[i]);
A[id[i]] = a[i];
}
int m = *max_element(id.begin(),id.end());
vector<int> b(m + 1);
DOWN(i,n-1,-1,1)
{
if(id[i] == m) b[m--] = a[i];
}
return b;
}

int main()
{
int a[] = {4,5,2,8,9,24,124,134};
vector<int> v(a,a + sizeof(a)/sizeof(int));
vector<int> result = lis_fast(v);
cout << result.size() << endl;
for(vector<int>::iterator it = result.begin(); it != result.end(); it++)
cout << *it << " ";
system("pause");
}