LCS, LIS

lcs-space-optimized.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
	string a, b; cin >> a >> b;
	int m = a.size(), n = b.size();
	vector<int> prev(n + 1, 0);
	vector<int> curr(n + 1, 0);

	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			if (a[i - 1] == b[j - 1]) {
				curr[j] = prev[j - 1] + 1;
			} else {
				curr[j] = max(curr[j - 1], prev[j]);
			}
		}

		swap(prev, curr);
	}

	cout << prev[m] << endl;

	return 0;
}

lcs.cpp

#include <bits/stdc++.h>
using namespace std;

string a, b;
void trace(vector<vector<char>> &t, int i, int j) {
	if (t[i][j] == 'u') trace(t, i - 1, j);
	else if (t[i][j] == 'l') trace(t, i, j - 1);
	else if (t[i][j] == 'c') {
		trace(t, i - 1, j - 1);
		cout << a[i - 1];
	}
}

int main() {
	cin >> a >> b;
	int m = a.size(), n = b.size();
	vector<vector<int>> c(m + 1, vector<int>(n + 1, 0));
	vector<vector<char>> t(m + 1, vector<char>(n + 1, '#'));

	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			if (a[i - 1] == b[j - 1]) {
				c[i][j] = c[i - 1][j - 1] + 1;
				t[i][j] = 'c';
			} else if (c[i - 1][j] >= c[i][j - 1]) {
				c[i][j] = c[i - 1][j];
				t[i][j] = 'u';
			} else {
				c[i][j] = c[i][j - 1];
				t[i][j] = 'l';
			}
		}
	}

	trace(t, m, n);

	return 0;
}

lis.cpp

#include <bits/stdc++.h>
using namespace std;

void trace(vector<int> &arr, vector<int> &prev, int i) {
	if (prev[i] == -1) {
		cout << arr[i] << " ";
		return;
	}
	trace(arr, prev, prev[i]);
	cout << arr[i] << " ";
}

int main() {
	int n; cin >> n;
	vector<int> v(n);
	vector<int> l(n, 1);
	vector<int> prev(n, -1);
	for (auto &d : v) cin >> d;

	for (int i = 1; i < n; i++) {
		for (int j = 0; j < i; j++) {
			if (v[i] > v[j] && l[i] < l[j] + 1) {
				l[i] = l[j] + 1;
				prev[i] = j;
			}
		}
	}

	auto i = max_element(l.begin(), l.end()) - l.begin();
	trace(v, prev, i);

	return 0;
}