summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2018-12-25 15:56:40 -0600
committerHaidong Ji2018-12-25 15:56:40 -0600
commite3e21cb0f76d24bc365898efe5a45b59226da00e (patch)
treee36e72d0c54aa1d59a1f3aea7574a30302983740
parent1c6c9657a6432fc1d7069ddf8dd106f7a614fbed (diff)
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.
-rw-r--r--AlgoDesignAndTechniqueEdxJava/sources/LCS3.java50
-rw-r--r--AlgoDesignAndTechniqueEdxJava/tests/LCS3Test.java23
2 files changed, 73 insertions, 0 deletions
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));
+ }
+
+}