notebook/code/LongestIncreasingSubsequence.cpp

// Given a list of numbers of length n, this routine extracts a
// longest increasing subsequence.
// Running time: O(n log n)
int A[MAX_N], indice[MAX_N], back[MAX_N];
VI lis(VI values, bool strict) {
	int N = values.size();
	int k = 0;
	fill_n(back, N, -1);
	for(int i = 0; i < N ; i++) {
		int j;
		if(strict)
			j = lower_bound(A, A + k, values[i]) - A;
		else
			j = upper_bound(A, A + k, values[i]) - A;
		if(j == k) {
			A[k] = values[i];
			indice[k] = i;
			++k;
		} else if(values[i] < A[j]) {
			A[j] = values[i];
			indice[j] = i;
		}
		if(i && j && j-1 < k)
			back[i] = indice[j-1];
	}
	VI  longest(k);
	int  cur = indice[k-1];
	for(int i = longest.size()-1; i >= 0; i--) {
		longest[i] = values[cur];
		cur = back[cur];
	}
	return  longest;
}