longestCommonSubSequenceDP.java

import java.util.*;

public class LCS2 
{
    /* 
    * As usual for DP, three Steps are involved:
    * 1. Break down the main problem into sub problems.
    * 2. Initialize cache to hold solutions to sub problems.
    * 3. Build solution to main problem from sub problem.
    * Refer to this https://youtu.be/ASoaQq66foQ (Back To Back SWE)
    */
    private static int lcs2(int[] a, int[] b) 
    {
        // a & b represent two strings.
        // longestCommonSubSequence is a axb matrix of two strings.
        int [][] longestCommonSubSequence = new int [a.length + 1][b.length + 1];

        // Initialize all all elements in first column to zero.
        for (int i = 0; i <= a.length; i++) 
        {
            longestCommonSubSequence[i][0] = 0;
        }

        // Initialize all all elements in first row to zero.
        for (int j = 0; j <= b.length; j++) 
        {
            longestCommonSubSequence[0][j] = 0;
        }
        // Iterate through each character of a
        for (int i = 1; i <= a.length; i++) 
        {
            // Iterate through each character of b for each element of a.
            for (int j = 1; j <= b.length; j++) 
            {
                // The subproblem is to look at the last character of each string.
                // Two possibilites exist, they can be equal, they need not be equal.
                if (a[i-1] == b[j-1]) 
                {
                    // as they are equal, simply do 1 + longestCommonSubSequence(subProblem).
                    longestCommonSubSequence[i][j] = longestCommonSubSequence[i-1][j-1] + 1;
                }
                else 
                {
                    // If they are not equal, check if removing of the last character from either of two strings yields longest commond subsequence.
                    longestCommonSubSequence[i][j] = Math.max(longestCommonSubSequence[i-1][j], longestCommonSubSequence[i][j-1]);
                }
            }
        }
        return longestCommonSubSequence[a.length][b.length];
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }

        int m = scanner.nextInt();
        int[] b = new int[m];
        for (int i = 0; i < m; i++) {
            b[i] = scanner.nextInt();
        }

        System.out.println(lcs2(a, b));
    }
}