Longest Common Subsequence problem using recursion with memorization.

LongestCommonSubsequenceWithMemorization.java

import java.util.Arrays;

public class LongestCommonSubsequenceWithMemorization {
	private static char[] A;
	private static char[] B;
	private static int[][] arr;
	
	private static int longestCommonSubsequent(int i, int j) {
		if (i == A.length || j == B.length) {
			return 0;
		} else if (arr[i][j] != -1) {
			return arr[i][j];
		} else if (A[i] == B[j]) {
			arr[i][j] =  1 + longestCommonSubsequent(i + 1, j + 1);
			return arr[i][j];
		} else {
			arr[i][j] = Integer.max(longestCommonSubsequent(i + 1, j), longestCommonSubsequent(i, j + 1));
			return arr[i][j];
		}
	}
	
	public static void main(String[] args) {
		A = "bd".toCharArray();
		B = "abcd".toCharArray();
		arr = new int[A.length][B.length];
		Arrays.stream(arr).forEach(i -> Arrays.fill(i, -1));
		
		System.out.println(longestCommonSubsequent(0, 0));
		System.out.println("Memory: " + Arrays.deepToString(arr));
	}
}