LIS

LISは最長増加部分列のことです。
ある配列が与えられたときに最長の増加部分列の長さをO(NlogN)で得ることができます。
動的計画法を普通に用いてもO(N^2)にしかならないのでより高速です。
最長増加部分列は複数存在する場合もありますがその１つを復元することが可能です。

d[x]は最初すべてありえない大きな値を入れておきます。
d[x]=y のとき、xの長さの部分列ができるときの最右の値の最小値を更新していきます。

例えば、

#define INF 10000

int a[6] = {1,4,3,6,5,2}; // のとき
int d[7];

for(int i = 0; i < 7; i++){
	d[i] = INF;
}

for(int i = 0; i < 6; i++){
	*lower_bound(d,d+7,a[i])=a[i];
}

結果は次のようになります。

d[0]=1,d[1]=2,d[2]=5,d[3]=INF,d[4]=INF,d[5]=INF,d[6]=INF

長さ1で最後の値が1になる増加部分列は存在する。
長さ2で最後の値が2になる増加部分列は存在する。
長さ3で最後の値が5になる増加部分列は存在する。

以上のことが言えます。
よってLISの最長は3になります。

復元は条件のあうものをより右から採用すれば良いので、
右から左へ探索して値を拾っていきます。

int m = 2;
vector<int> v;

for(int i = 5; i >=0; i--){
	if(d[m]<=a[i]&&a[i]<d[m+1]){
		v.push_back(a[i]);
		m--;
	}
}

reverse(v.begin(),v.end());

lower_boundは増加列内の値の重複を許しません。例えば1,2,3,4など。
upper_boundにすると増加列内の値の重複を許します。例えば1,1,1,2,3,3,4など。