From 1c6c9657a6432fc1d7069ddf8dd106f7a614fbed Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Tue, 25 Dec 2018 11:12:42 -0600
Subject: Longest Subsequence (betwee 2) done!

This one is pretty tricky. I solved it after reading online:
http://www.cs.umd.edu/~meesh/351/mount/lectures/lect25-longest-common-subseq.pdf
https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/

To find a good test case that reveals the bug, I tried stress testing
(in commented out code), but the naive but correct algo is so
inefficient that I didn't have enough patience to let it finish. Anyway,
good practice of stress testing anyway.---
 AlgoDesignAndTechniqueEdxJava/sources/LCS2.java   | 56 ++++++++++++++++++++++-
 AlgoDesignAndTechniqueEdxJava/tests/LCS2Test.java | 52 ++++++++++++++++-----
 2 files changed, 95 insertions(+), 13 deletions(-)

diff --git a/AlgoDesignAndTechniqueEdxJava/sources/LCS2.java b/AlgoDesignAndTechniqueEdxJava/sources/LCS2.java
index d214eff..e2a882c 100644
--- a/AlgoDesignAndTechniqueEdxJava/sources/LCS2.java
+++ b/AlgoDesignAndTechniqueEdxJava/sources/LCS2.java
@@ -1,4 +1,6 @@
+import java.util.Arrays;
 import java.util.Scanner;
+//import java.util.concurrent.ThreadLocalRandom;
 
 public class LCS2 {
 
@@ -16,7 +18,33 @@ public class LCS2 {
             b[i] = scanner.nextInt();
         }
 
-        System.out.println(lcs2(a, b));
+        System.out.println(third_lcs2(a, b));
+//        System.out.println(alt_lcs2(a, b, n, m));
+
+//        while (true) {
+////            int n = ThreadLocalRandom.current().nextInt(1, 101);
+////            int m = ThreadLocalRandom.current().nextInt(1, 101);
+//            int n = ThreadLocalRandom.current().nextInt(1, 20);
+//            int m = ThreadLocalRandom.current().nextInt(1, 20);
+//            int[] a = new int[n];
+//            int[] b = new int[m];
+//            for (int i = 0; i < a.length; i++) {
+//                a[i] = ThreadLocalRandom.current().nextInt(-999999999, 1000000000);
+//            }
+//            for (int i = 0; i < b.length; i++) {
+//                b[i] = ThreadLocalRandom.current().nextInt(-999999999, 1000000000);
+//            }
+//            int r1 = lcs2(a, b);
+//            int r2 = alt_lcs2(a, b, n, m);
+//            if (r1 == r2)
+//                System.out.println("ok");
+//            else {
+//                System.out.println(Arrays.toString(a));
+//                System.out.println(Arrays.toString(b));
+//                System.out.println("Wrong answer " + r1 + " " + r2);
+//                break;
+//            }
+//        }
     }
 
     public static int[][] editDistance(int[] A, int[] B) {
@@ -66,4 +94,30 @@ public class LCS2 {
             return lcs2(i - 1, j - 1, D);
     }
 
+    public static int alt_lcs2(int[] a, int[] b, int i, int j) {
+        if (i == 0 || j == 0)
+            return 0;
+        if (a[i - 1] == b[j - 1])
+            return 1 + alt_lcs2(a, b, i - 1, j - 1);
+        else
+            return Math.max(alt_lcs2(a, b, i, j - 1), alt_lcs2(a, b, i - 1, j));
+    }
+
+    public static int third_lcs2(int[] a, int[] b) {
+        int m = b.length;
+        int n = a.length;
+        int[][] D = new int[n + 1][m + 1];
+        for (int j = 1; j < m + 1; j++) {
+            for (int i = 1; i < n + 1; i++) {
+                if (a[i - 1] == b[j - 1]) {
+                    D[i][j] = D[i - 1][j - 1] + 1;
+                } else {
+                    D[i][j] = Math.max(D[i - 1][j], D[i][j - 1]);
+                }
+            }
+        }
+
+        return D[n][m];
+    }
+
 }
diff --git a/AlgoDesignAndTechniqueEdxJava/tests/LCS2Test.java b/AlgoDesignAndTechniqueEdxJava/tests/LCS2Test.java
index bdfa799..83de106 100644
--- a/AlgoDesignAndTechniqueEdxJava/tests/LCS2Test.java
+++ b/AlgoDesignAndTechniqueEdxJava/tests/LCS2Test.java
@@ -6,30 +6,58 @@ class LCS2Test {
 
     @Test
     void test() {
-        int[] a = {2, 7, 5};
-        int[] b = {2, 5};
-        assertEquals(2, LCS2.lcs2(a,b));
+        int[] a = { 2, 7, 5 };
+        int[] b = { 2, 5 };
+        assertEquals(2, LCS2.lcs2(a, b));
+        assertEquals(2, LCS2.third_lcs2(a, b));
+        assertEquals(2, LCS2.alt_lcs2(a, b, 3, 2));
     }
 
     @Test
     void test1() {
-        int[] a = {7};
-        int[] b = {1, 2, 3, 4};
-        assertEquals(0, LCS2.lcs2(a,b));
+        int[] a = { 7 };
+        int[] b = { 1, 2, 3, 4 };
+        assertEquals(0, LCS2.lcs2(a, b));
+        assertEquals(0, LCS2.third_lcs2(a, b));
+        assertEquals(0, LCS2.alt_lcs2(a, b, 1, 4));
     }
 
     @Test
     void test2() {
-        int[] a = {2, 7, 8, 3};
-        int[] b = {5, 2, 8, 7};
-        assertEquals(2, LCS2.lcs2(a,b));
+        int[] a = { 2, 7, 8, 3 };
+        int[] b = { 5, 2, 8, 7 };
+        assertEquals(2, LCS2.lcs2(a, b));
+        assertEquals(2, LCS2.third_lcs2(a, b));
+        assertEquals(2, LCS2.alt_lcs2(a, b, 4, 4));
     }
 
     @Test
     void test3() {
-        int[] a = {1, 2, 3, 4, 5, 6, 7};
-        int[] b = {1, 2, 8, 4, 5, 6};
-        assertEquals(5, LCS2.lcs2(a,b));
+        int[] a = { 1, 2, 3, 4, 5, 6, 7 };
+        int[] b = { 1, 2, 8, 4, 5, 6 };
+        assertEquals(5, LCS2.lcs2(a, b));
+        assertEquals(5, LCS2.third_lcs2(a, b));
+        assertEquals(5, LCS2.alt_lcs2(a, b, 7, 6));
+    }
+
+    @Test
+    void test4() {
+        int[] a = { 1, 9, 2, 5, 5, 5, 8, 3, 5, 11, 0, 2, 4, 1, 7, 4, 5, 9, 2, 4, 0, 3, 1, 5, 8, 3, 5, 9, 7, 8, 4, 5, 6,
+                7 };
+        int[] b = { 6, 3, 8, 3, 1, 8, 3, 5, 0, 9, 6, 8, 3, 5, 7, 9, 1, 4, 7, 9, 3, 5, 9, 0, 1, 4, 2, 7, 5, 8, 9, 3, 5,
+                6, 1, 6, 3, 1, 6, 7, 3 };
+        assertEquals(16, LCS2.lcs2(a, b));
+        assertEquals(17, LCS2.third_lcs2(a, b));
+//        assertEquals(5, LCS2.alt_lcs2(a, b, a.length, b.length));
+    }
+
+    @Test
+    void test5() {
+        int[] a = { 2, 4, 3, 3 };
+        int[] b = { 1, 4, 3 };
+        assertEquals(2, LCS2.lcs2(a, b));
+        assertEquals(2, LCS2.third_lcs2(a, b));
+//        assertEquals(5, LCS2.alt_lcs2(a, b, a.length, b.length));
     }
 
 }
-- 
cgit v1.2.3