From b12193500c0da24a9e7fc5a8523ed2252da88bad Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Tue, 25 Dec 2018 14:27:29 -0600
Subject: Longest subsequence of 2 seqs done!

Not too bad, since I worked it out in Java already.---
 AlgoDesignAndTechniqueEdxPython/sources/lcs2.py | 35 +++++++++++++++++++++++++
 1 file changed, 35 insertions(+)
 create mode 100644 AlgoDesignAndTechniqueEdxPython/sources/lcs2.py

(limited to 'AlgoDesignAndTechniqueEdxPython/sources/lcs2.py')

diff --git a/AlgoDesignAndTechniqueEdxPython/sources/lcs2.py b/AlgoDesignAndTechniqueEdxPython/sources/lcs2.py
new file mode 100644
index 0000000..76f73fd
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/sources/lcs2.py
@@ -0,0 +1,35 @@
+# Uses python3
+
+import sys
+
+
+def getLCS2Length(a, b):
+    m = len(b)
+    n = len(a)
+
+    D = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
+    
+    for j in range(1, m + 1):
+        for i in range(1, n + 1):
+            if a[i - 1] == b[j - 1]:
+                D[i][j] = D[i - 1][j - 1] + 1
+            else:
+                D[i][j] = max(D[i - 1][j], D[i][j - 1])
+
+    return D[n][m]
+
+
+if __name__ == '__main__':
+    input = sys.stdin.read()
+    data = list(map(int, input.split()))
+
+    n = data[0]
+    data = data[1:]
+    a = data[:n]
+
+    data = data[n:]
+    m = data[0]
+    data = data[1:]
+    b = data[:m]
+
+    print(getLCS2Length(a, b))
-- 
cgit v1.2.3