Longest Common Subsequence (LCS) Problem Statement
Given two sequences and , we need to find the length of their .
Given two sequences and , we need to find the length of their .
For example, for the sequences and , one longest common subsequence is .
Let dp(i, j) denote the answer for:
a of length i;b of length j.In other words, dp(i, j) is the length of the longest common subsequence of
and
If one of the prefixes is empty, then the answer is 0:
Now consider the general case , where and .
There are three possibilities:
a[i] is not used in the answer, so we transition from dp(i - 1, j);b[j] is not used in the answer, so we transition from dp(i, j - 1);a[i] and b[j] are used in the answer. This is possible only if a[i] == b[j], and then we transition from dp(i - 1, j - 1) + 1.So the recurrence is:
To restore one actual longest common subsequence, we can remember which transition was best for each state.
Let p(i, j) store the transition used to get dp(i, j):
1 means we came from dp(i - 1, j);2 means we came from dp(i, j - 1);3 means we came from dp(i - 1, j - 1) + 1.Then we start from (n, m) and move backward until one of the indices becomes zero.
p(x, y) == 3, then a[x] belongs to the answer, so we add it and move to (x - 1, y - 1);p(x, y) == 2, we move to (x, y - 1);p(x, y) == 1, we move to (x - 1, y).Given a sequence
we need to find its longest increasing subsequence.
For example, for the sequence
one longest increasing subsequence is
One possible idea is to create a sorted copy of the sequence and compute the LCS between the original sequence and the sorted one.
This idea is useful conceptually, but in practice it is not the standard way to solve LIS.
Let dp(i) denote the length of the longest increasing subsequence in the prefix
under the condition that a[i] is included in the subsequence.
So a[i] must be the last element of the subsequence counted by dp(i).
If the subsequence contains only a[i], then:
To compute dp(i), we try all earlier positions j < i such that
If we place a[i] after a[j], then we get:
So the recurrence is:
The final answer is:
To restore one actual LIS, we store the best previous position for each i.
Let p(i) mean:
0, if the subsequence ending at i consists only of a[i];j, if the best transition is from position j.Then after computing dp, we find the position x where dp[x] is maximum, and follow the parent pointers backward.
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j] = 0;
dp[i][j] = max(dp[i][j], dp[i - 1][j]);
dp[i][j] = max(dp[i][j], dp[i][j - 1]);
if (a[i] == b[j]) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j] = -1;
if (dp[i - 1][j] > dp[i][j]) {
dp[i][j] = dp[i - 1][j];
p[i][j] = 1;
}
if (dp[i][j - 1] > dp[i][j]) {
dp[i][j] = dp[i][j - 1];
p[i][j] = 2;
}
if (a[i] == b[j] && dp[i - 1][j - 1] + 1 > dp[i][j]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
p[i][j] = 3;
}
}
}
vector<int> res;
int x = n, y = m;
while (x > 0 && y > 0) {
if (p[x][y] == 3) {
res.push_back(a[x]);
x -= 1;
y -= 1;
} else if (p[x][y] == 2) {
y -= 1;
} else { // p[x][y] == 1
x -= 1;
}
}
reverse(res.begin(), res.end());
for (int i = 1; i <= n; i++) {
dp[i] = 1;
for (int j = 1; j < i; j++) {
if (a[j] < a[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
for (int i = 1; i <= n; i++) {
dp[i] = 1;
p[i] = 0;
for (int j = 1; j < i; j++) {
if (a[j] < a[i] && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
p[i] = j;
}
}
}
int x = 1;
for (int i = 1; i <= n; i++) {
if (dp[i] > dp[x]) {
x = i;
}
}
vector<int> res;
while (x > 0) {
res.push_back(a[x]);
x = p[x];
}
reverse(res.begin(), res.end());