The Longest Common Subsequence

/**
 * Problem Statement

A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. Longest common subsequence (LCS) of 2 sequences is a subsequence, with maximal length, which is common to both the sequences. 

Given two sequence of integers, A=[a1,a2,…,an] and B=[b1,b2,…,bm], find any one longest common subsequence.

In case multiple solutions exist, print any of them. It is guaranteed that at least one non-empty common subsequence will exist.

Input Format

First line contains two space separated integers, n and m, where n is the size of sequence A, while m is size of sequence B. In next line there are n space separated integers representing sequence A, and in third line there are m space separated integers representing sequence B.

n m
A1 A2 … An 
B1 B2 … Bm  
Constraints

1≤n≤100 
1≤m≤100 
0≤ai<1000,where i∈[1,n] 
0≤bj<1000,where j∈[1,m]

Output Format

Print the longest common subsequence and each element should be separated by at least one white-space. In case of multiple answers, print any one of them.

Sample Input

5 6
1 2 3 4 1
3 4 1 2 1 3
Sample Output

1 2 3
Explanation

There is no common subsequence with length larger than 3. And "1 2 3", "1 2 1", "3 4 1" are all correct answers.


 */
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

	public static String backTrack(int[][] arr, int[] arr1, int[] arr2, int n, int m)
	{
		if(m == 0 || n == 0)
			return "";
		else {
			if(arr1[n] == arr2[m])
				return backTrack(arr, arr1, arr2, n-1, m-1) + " " + arr1[n];
			else {
				if(arr[n-1][m] > arr[n][m-1])
					return backTrack(arr, arr1, arr2, n-1, m);
				else
					return backTrack(arr, arr1, arr2, n, m-1);
			}
		}
	}
	
    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] arr1 = new int[n+1];
        int[] arr2 = new int[m+1];
        int[][] arr = new int[n+1][m+1];
        in.nextLine();
        String string = new String(in.nextLine());
        String[] str = string.split(" ");
        for (int i = 1; i <= n; i++) {
			arr1[i] = Integer.parseInt(str[i-1]);
		}
        string = in.nextLine();
        str = string.split(" ");
        for (int i = 1; i <= m; i++) {
			arr2[i] = Integer.parseInt(str[i-1]);
		}
        for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if(arr1[i] == arr2[j])
					arr[i][j] = arr[i-1][j-1] + 1;
				else {
					if(arr[i-1][j] > arr[i][j-1])
						arr[i][j] = arr[i-1][j];
					else
						arr[i][j] = arr[i][j-1];
				}
			}
		}
        
      
        System.out.println(backTrack(arr, arr1, arr2, n, m).substring(1));
        
    }
}