Implement the solution to the Longest Common Increasing Subsequence (LCIS) problem using dynamic programming.?

The Longest Common Increasing Subsequence (LCIS) problem asks us to find the length of the longest common subsequence of two given sequences such that the common subsequence is increasing.

Dynamic programming is a natural way to solve this problem. We can start by defining a 2D array ‘dp‘ where ‘dp[i][j]‘ represents the length of the LCIS of the first i elements of the first sequence and the first j elements of the second sequence.

To fill up the ‘dp‘ array, we can use the following recurrence relation:

if seq1[i] == seq2[j]:
    dp[i][j] = 1 + max(dp[k][l]) where k < i and l < j
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

The intuition behind this recurrence relation is as follows. If the ith element of the first sequence and jth element of the second sequence are equal, then the length of the LCIS will be the length of the LCIS up to the (i-1)th element of the first sequence and (j-1)th element of the second sequence plus one. We can calculate this value for all previous i and j and take the maximum to get the final value of ‘dp[i][j]‘.

If the ith element of the first sequence and jth element of the second sequence are not equal, then we need to consider two cases - either we include the ith element of the first sequence or the jth element of the second sequence in the LCIS. We take the maximum of the length of the LCIS with and without including the ith element and the length of the LCIS with and without including the jth element to get the final value of ‘dp[i][j]‘.

The final answer would be the maximum value in the ‘dp‘ array.

Here’s the Java implementation of the LCIS problem:

public static int LCIS(int[] seq1, int[] seq2) {
    int m = seq1.length, n = seq2.length;
    int[][] dp = new int[m+1][n+1];
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (seq1[i-1] == seq2[j-1]) {
                int maxVal = 0;
                for (int k = 0; k < i-1; k++) {
                    for (int l = 0; l < j-1; l++) {
                        if (seq1[k] < seq1[i-1] && seq2[l] < seq2[j-1]) {
                            maxVal = Math.max(maxVal, dp[k][l]);
                        }
                    }
                }
                dp[i][j] = 1 + maxVal;
            }
            else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    
    int ans = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            ans = Math.max(ans, dp[i][j]);
        }
    }
    return ans;
}

In this implementation, we are iterating over all possible values of ‘i‘ and ‘j‘ and filling up the ‘dp‘ array. Then we iterate over the entire ‘dp‘ array again to find the maximum value, which is the solution to the LCIS problem.