Instantly share code, notes, and snippets.

Embed
What would you like to do?
Generic longest increasing subsequence (LIS) dynamic programming solution (O(n^2) time)
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment