LCS - Longest Common Subsequence - Dynamic Programming

https://practice.geeksforgeeks.org/problems/longest-common-subsequence/0/?ref=self

	/*package whatever //do not write package name here */
	import java.util.*;
	import java.lang.*;
	import java.io.*;
	class GFG {
	public static void main(String[] args) {
	//code
	Scanner scanner = new Scanner(System.in);
	int T = scanner.nextInt();
	for (int t = 0; t < T; t++) {
	int m = scanner.nextInt();
	int n = scanner.nextInt();
	if (m < 1) {
	System.out.println(n);
	} else if (n < 1) {
	System.out.println(m);
	}
	String string1 = scanner.next();
	String string2 = scanner.next();
	int[][] dp = new int[m][n];
	int globalMax = 0;
	for (int i = 0; i < m; i++) {
	for (int j = 0; j < n; j++) {
	if (string1.charAt(i) == string2.charAt(j)) {
	int localMax = 0;
	for (int x = 0; x < i; x++) {
	for (int y = 0; y < j; y++) {
	localMax = Math.max(localMax, dp[x][y]);
	}
	}
	dp[i][j] = localMax + 1;
	globalMax = Math.max(globalMax, dp[i][j]);
	}
	}
	}
	// System.out.println(Arrays.toString(dp));
	System.out.println(globalMax);
	}
	}
	}

view raw LCS - Longest Common Subsequence - Dynamic Programming.java hosted with ❤ by GitHub