From e3e21cb0f76d24bc365898efe5a45b59226da00e Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Tue, 25 Dec 2018 15:56:40 -0600
Subject: Longest subsequence (3 seqs) done!

Not too bad after case for 2 seqs is done. Just needed to add one more
dimension and take care to set values.---
 AlgoDesignAndTechniqueEdxJava/sources/LCS3.java   | 50 +++++++++++++++++++++++
 AlgoDesignAndTechniqueEdxJava/tests/LCS3Test.java | 23 +++++++++++
 2 files changed, 73 insertions(+)
 create mode 100644 AlgoDesignAndTechniqueEdxJava/sources/LCS3.java
 create mode 100644 AlgoDesignAndTechniqueEdxJava/tests/LCS3Test.java

diff --git a/AlgoDesignAndTechniqueEdxJava/sources/LCS3.java b/AlgoDesignAndTechniqueEdxJava/sources/LCS3.java
new file mode 100644
index 0000000..30ad31f
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/sources/LCS3.java
@@ -0,0 +1,50 @@
+import java.util.Scanner;
+
+public class LCS3 {
+
+    public static void main(String[] args) {
+        Scanner scanner = new Scanner(System.in);
+        int an = scanner.nextInt();
+        int[] a = new int[an];
+        for (int i = 0; i < an; i++) {
+            a[i] = scanner.nextInt();
+        }
+        int bn = scanner.nextInt();
+        int[] b = new int[bn];
+        for (int i = 0; i < bn; i++) {
+            b[i] = scanner.nextInt();
+        }
+        int cn = scanner.nextInt();
+        int[] c = new int[cn];
+        for (int i = 0; i < cn; i++) {
+            c[i] = scanner.nextInt();
+        }
+        System.out.println(lcs3(a, b, c));
+    }
+
+    public static int lcs3(int[] a, int[] b, int[] c) {
+
+        int l = c.length;
+        int m = b.length;
+        int n = a.length;
+        int[][][] D = new int[n + 1][m + 1][l + 1];
+        for (int k = 0; k < l + 1; k++) {
+            for (int j = 0; j < m + 1; j++) {
+                for (int i = 0; i < n + 1; i++) {
+                    if (i == 0 || j == 0 || k == 0) {
+                        D[i][j][k] = 0;
+                        continue;
+                    }
+                    if (a[i - 1] == b[j - 1] && b[j - 1] == c[k - 1]) {
+                        D[i][j][k] = D[i - 1][j - 1][k - 1] + 1;
+                    } else {
+                        D[i][j][k] = Math.max(D[i - 1][j][k], Math.max(D[i][j - 1][k], D[i][j][k - 1]));
+                    }
+                }
+            }
+        }
+
+        return D[n][m][l];
+    }
+
+}
diff --git a/AlgoDesignAndTechniqueEdxJava/tests/LCS3Test.java b/AlgoDesignAndTechniqueEdxJava/tests/LCS3Test.java
new file mode 100644
index 0000000..b238403
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/tests/LCS3Test.java
@@ -0,0 +1,23 @@
+import static org.junit.jupiter.api.Assertions.*;
+
+import org.junit.jupiter.api.Test;
+
+class LCS3Test {
+
+    @Test
+    void test() {
+        int[] a = { 1, 2, 3 };
+        int[] b = { 2, 1, 3 };
+        int[] c = { 1, 3, 5 };
+        assertEquals(2, LCS3.lcs3(a, b, c));
+    }
+
+    @Test
+    void test1() {
+        int[] a = { 8, 3, 2, 1, 7 };
+        int[] b = { 8, 2, 1, 3, 8, 10, 7 };
+        int[] c = { 6, 8, 3, 1, 4, 7 };
+        assertEquals(3, LCS3.lcs3(a, b, c));
+    }
+
+}
-- 
cgit v1.2.3