Longest Common Increasing Subsequence(LCIS)

This is an interesting and challenging dynamic programming problem: Codeforces 10D LCIS.

The description of the problem is long, here is a simplified version:

You are given two sequences of integer numbers. You are to find their longest common increasing subsequence(LCIS), i.e. an increasing sequence of maximum length that is the subsequence of both sequences.

For example:

sequence a: 2 3 1 6 5 4 6 
sequence b: 1 3 5 6
LCIS of a and b: 3 5 6


sequence a: 1 2 0 2 1
sequence b: 1 0 1 
LCIS of a and b: 0 1

Why is it interesting?

I believe people who have a certain foundation in dynamic programming have done these two basic problems:

• LIS (Longest Increasing Subsequence)
• LCS (Longest Common Subsequence)

The problem is asking for LCIS (Longest Common Increasing Subsequence), which seems like a combination of the LIS and LCS problems.

My initial idea was to first find the LCS of the two sequences, and then find the LIS of that subsequence. However, this failed due to the following counterexample:

sequence a: 3 2 1 4 
sequence b: 3 4 2 1

The LCS is 3 2 1, but the LCIS is 3 4. The reason is that LCIS is not necessarily within LCS.

Later, I further thought about whether we could first separately find the LIS of each sequence and then find the LCS of these two LISs. However, this approach doesn’t work because each sequence’s LIS may have multiple solutions. We need to look for a new algorithm.

Solution

In dynamic programming, problems related to sequences can generally be considered based on the current element being the endpoint, such as:

• In the LCS problem, f[i][j] represents the length of the longest common subsequence of the first sequence up to the i-th element and ending with i, and the second sequence up to the j-th element and ending with j, the state transition equation is as follows:

• In the LIS problem, f[i] represents the length of the longest increasing subsequence ending with the i-th element among the first i elements. The state transition equation is as follows:

For the LCIS problem, if we consider setting f[i][j] as the length of the LCIS obtained by selecting from the first i elements of sequence a and first j elements of sequence b, similar to LCS, but this is not conducive to state transition.

Therefore, based on the idea of LIS, we set f[i][j] as the length of the LCIS obtained by selecting from the first i elements of sequence a and ending with b[j].

There are two cases:

• When a[i] != b[j], we cannot choose a[i] (because the LCIS ends with b[j], b[j] must be chosen, so a[i] cannot be chosen), i.e.:

• When a[i] == b[j], we enumerate the possible subsequences ending with b[k](k < j) and check if we can add a[i] (i.e., b[j]) into it (note that this article is 1-indexed):

Overall, the state transition equation is:

Then we can write an O(n³) algorithm:

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

In the above code, the key part is the for(int k=1; k<j; k++) loop.

Consider: sequence a:[2, 3, 1, 7, 6] and sequence b: [1, 4, 6, 6]

• When i = 5, j = 3, a[5] = b[3], k traverses from 1 to 2 to find the maximum f[i-1][k]. (Note that this article is 1-indexed)
• When i = 5, j = 4, a[5] = b[4], k traverses from 1 to 3 to find the maximum f[i-1][k], where the loop from 1 to 2 is a repeated traversal, as shown in the green area in Figure 1, because a[5] is unchanged, and the elements where b[k] < a[5] are fixed when k traverses from 1 to 2, and no state transition occurs:

Figure 1: repeated traversal

Actually, we can use a variable fmax to store the maximum value of f[i-1][k] for the first j-1 elements. In other words, we save the maximum value of f[i-1][k] in the green area of Figure 1. By doing this, we can eliminate the loop for k.

Next, let’s consider how to output the path for the DP problem. In fact, the path for the DP problem is quite simple. We just need to keep track of how each state is transitioned, in other words, record the previous state.

Code as follows:

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

const int N = 5005;

int n, m, a[N], b[N];
int f[N][N], pre[N][N];

int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
 
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
 
    cin >> m;
    for (int j = 1; j <= m; ++j)
        cin >> b[j];
  
  /* O(n^3) solution
  for(int i = 1; i <= n; ++i)
    for(int j = 1; j <= m; ++j) 
    {
      if(a[i] == b[j]) 
      {
        for(int k = 0; k < j; ++k)
          if(a[i] > b[k])
            f[i][j] = max(f[i][j], f[i-1][k]+1);
      }
      else f[i][j] = f[i-1][j];
    }
  */
  
    // O(n^2) solution
    for (int i = 1; i <= n; ++i)
    {
        int fmax = 0, pos = 0;
        for (int j = 1; j <= m; j++)
        {
            f[i][j] = f[i - 1][j];     // Exclude a[i] from LCIS
            pre[i][j] = pre[i-1][j];
            if (a[i] == b[j])
            {   // Add a[i] to LCIS
            // fmax is the maximum value of the O(n^3) solution f[i-1][k]+1
                if (f[i][j] < fmax + 1) 
                {
                    f[i][j] = fmax + 1;
                    // Prepare for the output path, record the index of the 
                    // previous element of the LCIS ending with b[j] among the
                    // first j elements of b, which is also an element of the 
                    // first i elements of a.
                    pre[i][j] = pos;  
                }
            }
            if (b[j] < a[i])
            {
                if (f[i - 1][j] > fmax)
                {
                // fmax is the maximum value of the O(n^3) solution f[i-1][k]+1
                    fmax = f[i - 1][j]; 
                    pos = j;
                }
            }
        }
    }

    int res = 0, last = 0, tot = 0, path[N];

    // Looking for the length of LCIS and the position of the end of LCIS
    for (int j = 1; j <= m; ++j) 
    { 
        if (res < f[n][j])
        {
            res = f[n][j];
            last = j;
        }
    }

    cout << res << endl;

    int i = n, j = last;
    // Using the pre-array, find the entire sequence step by step based on
    // the last element of LCIS
    while (i || j) 
    {
        if (pre[i][j] != j)
            path[++tot] = b[j];
        j = pre[i][j];
        i--;
    }

    while (tot)
        cout << path[tot--] << ' ';
    cout << endl;

    return 0;
}

Conclusion

This article introduces an interesting dynamic programming problem that seems to be a combination of the Longest Increasing Subsequence (LIS) and Longest Common Subsequence (LCS) problems.

However, besides borrowing ideas from these two problems, it has significant differences, demonstrating the diverse and challenging nature of dynamic programming problems.

Dynamic programming is a core algorithm in computer science that requires a high level of proficiency, repeated practice, and the ability to apply it to different problems. More dynamic programming algorithm problems will be introduced in the future.

Furthermore, the latest AI-related content can be found in my newsletter.

Finally, if there are any mistakes in this article, please kindly provide feedback. Thank you.

Reference Materials

https://codeforces.com/problemset/problem/10/D