Longest Common Subsequence problem with Dynamic Programming.

LongestCommonSubsequenceWithDynamicProgramming.java

mport java.util.*;

public class LongestCommonSubsequenceWithDynamicProgramming {
	public static void main(String[] args) {
		char[] A = "bd".toCharArray();
		char[] B = "abcd".toCharArray();
		
		int[][] arr = new int[A.length + 1][B.length + 1];
		
		for (int i = 1; i <= A.length; i++) {
			for (int j = 1; j <= B.length; j++) {
				if (A[i - 1] == B[j - 1]) {
					arr[i][j] = 1 + arr[i - 1][j - 1];
				} else {
					arr[i][j] = Integer.max(arr[i - 1][j], arr[i][j - 1]);
				}
			}
		}
		
		System.out.println(arr[A.length][B.length]);
		System.out.println("Memory: " + Arrays.deepToString(arr));
		
		// Tracing
		List<Character> sequence = new ArrayList<>();
		int i = A.length;
		int j = B.length;
		
		while (i > 0 && j > 0) {
			if (arr[i][j] == arr[i - 1][j]) {
				i--;
			} else if (arr[i][j] == arr[i][j - 1]) {
				j--;
			} else if (arr[i][j] == arr[i - 1][j - 1] + 1) {
				sequence.add(A[i - 1]);
				i--;
				j--;
			}
		}
		
		Collections.reverse(sequence);
		System.out.println("Sequence: " + sequence);
	}
}