Generic longest increasing subsequence (LIS) dynamic programming solution (O(n^2) time)

generic-lis.cpp

#include <iostream>
#include <functional>
#include <deque>
#include <vector>

using namespace std;

template<typename T>
deque<T> find_lis(const vector<T> &a,
	function<bool(const T &, const T &)> comp = [&](const T &a, const T &b)->bool { return a < b; })
{
	int maxLength = 1, bestEnd = 0;

	vector<int> DP(a.size(), 1);
	vector<int> prev(a.size(), -1);

	for (int i = 1; i < a.size(); i++) {
		for (int j = i - 1; j >= 0; j--) {
			if (DP[j] + 1 > DP[i] && comp(a[j], a[i])) {
				DP[i] = DP[j] + 1;
				prev[i] = j;
			}
		}

		if (DP[i] > maxLength) {
			bestEnd = i;
			maxLength = DP[i];
		}
	}

	deque<T> lis;
	for (int i = bestEnd; i != -1; i = prev[i]) {
		lis.push_front(a[i]);
	}

	return lis;
}

int main()
{
	vector<int> a = { 30, 2, 6, 4, 5, 1 };
	auto lis_int = find_lis<int>(a);
	
	string str = "baaewzertaz";
	vector<char> seq; 
	for (auto &s : str) seq.push_back(s);
	auto lis_str = find_lis<char>(seq);

	cout << lis_int.size() << endl;
	for (auto &i : lis_int) cout << i << " ";
	cout << endl << endl;
	
	cout << lis_str.size() << endl;
	for (const auto &e : lis_str) cout << e << " ";
	cout << endl << endl;
	
	// longest decreasing subsequence
	lis_str = find_lis<char>(seq, [&](const char &a, const char &b)->bool { return a > b; });
	cout << lis_str.size() << endl;
	for (const auto &e : lis_str) cout << e << " ";
	cout << endl;
}