Longest Increasing Subsequence

• Time : O(nlogn)
• Space : O(n)

#include <vector>
using namespace std;

vector<int> longestIncreasingSubsequence(vector<int> array) {
  int n = array.size();
	vector<int> lis;
	vector<int> record(n);
	for(int i = 0; i < n; i++) {
		if(lis.empty() or lis.back() < array[i]) {
			lis.push_back(array[i]);
			record[i] = lis.size() - 1;
		} else {
			auto j = lower_bound(begin(lis), end(lis), array[i]) - begin(lis);
			lis[j] = array[i];
			record[i] = j;
		}
	}
	
	vector<int> res;
	for(int i = n - 1, r = lis.size() - 1; i >= 0; i--) {
		if(record[i] == r) {
			res.push_back(array[i]);
			r--;
		}
	}
	
	reverse(begin(res), end(res));
  return res;
}