new code for LIS

prakhar1989 · Aug 15, 2015 · a607355 · a607355
1 parent 64f0abf
commit a607355
Show file tree

Hide file tree

Showing 2 changed files with 18 additions and 24 deletions.
diff --git a/dp/kadane.py b/dp/kadane.py
@@ -1,4 +1,9 @@
 """
+Problem: The maximum subarray problem is the task of finding the
+contiguous subarray within a one-dimensional array of numbers
+(containing at least one positive number) which has the largest sum.
+
+Solution:
 The recurrence relation that we solve at each step is the following -
 
 Let S[i] = be the max value contigous subsequence till the ith element

diff --git a/dp/longest_subsequence.py b/dp/longest_subsequence.py
@@ -1,31 +1,20 @@
 def longest_seq(seq):
-    """ returns the longest increasing subseqence 
+    """ returns the longest increasing subseqence
     in a sequence """
-    count = [1] * len(seq)
-    prev = [0] * len(seq)
-    for i in range(1, len(seq)):
-        dist = []
-        temp_prev = {}
-        for j in range(i):
-            if seq[j] < seq[i]:
-                dist.append(count[j])
-                temp_prev[count[j]] = j
-            else:
-                temp_prev[0] = j
-                dist.append(0)
-        count[i] = 1 + max(dist)
-        prev[i] = temp_prev[max(dist)]
-
-    # path
-    path = [seq[prev.index(max(prev))]]
-    i = prev.index(max(prev))
-    while i>1:
-        path.append(seq[prev[i]])
-        i = prev[i]
-    return max(count), path[::-1]
+    cache = [1] * len(nums)
+    solution = [0] * len(nums)
+
+    for i in range(1, len(nums)):
+        for j in range(0, i):
+            if nums[i] > nums[j]:
+                if cache[j] + 1 > cache[i]:
+                    cache[i] = cache[j] + 1
+                    solution[i] = j
+    return max(cache), solution
 
 if __name__ == "__main__":
     seq = [5, 2, 8, 10, 3, 6, 9, 7]
     seq2 = [0, 8, 3, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]
-    print longest_seq(seq2)
+    seq3 = [10, 22, 9, 33, 21, 50, 41, 60, 80]
+    print longest_seq(seq3)