Updated code. Fixes prakhar1989#7

prakhar1989 · prakhar1989 · commit b81d2ca82023 · 2015-08-16T09:52:11.000+05:30
diff --git a/dp/longest_subsequence.py b/dp/longest_subsequence.py
@@ -1,20 +1,45 @@
-def longest_seq(seq):
-    """ returns the longest increasing subseqence
-    in a sequence """
+"""
+Problem: http://www.geeksforgeeks.org/dynamic-programming-set-3-longest-increasing-subsequence/
+"""
+def longest_increasing_subsequence(nums):
+    # array used to store the length of the longest subsequence found
     cache = [1] * len(nums)
-    solution = [0] * len(nums)
+
+    # array used to store the location of the predecessor in the longest
+    # subsequence. -1 by default
+    location = [-1] * 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
+                    location[i] = j
+
+    # finding the max in the cache gives us the 
+    # answer - i.e. length of the LIS
+    max_value = max(cache)
+
+    # with the answer in hand, we need to build the solution
+    # using the locations stored
+    solution = []
+    i = cache.index(max_value)
+
+    # we start with the max value i.e. the index of the 
+    # location where the max LIS exists and then
+    # keep backtracking to build up the solution
+    while location[i] > -1:
+        solution.append(nums[i])
+        i = location[i]
+
+    # when the loop ends, just append the starting element
+    solution.append(nums[i])
+
+    # return the length of the LIS and the solution (in reverse)
+    return max_value, solution[::-1]
 
 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]
-    seq3 = [10, 22, 9, 33, 21, 50, 41, 60, 80]
-    print longest_seq(seq3)
+    assert longest_increasing_subsequence([3, 4, -1, 0, 6, 2, 3]) == (4, [-1, 0, 2, 3])
+    assert longest_increasing_subsequence([10, 22, 9, 33, 21, 50, 41, 60, 80]) == (6, [10, 22, 33, 50, 60, 80])
+    assert longest_increasing_subsequence([5,0,1,2,3,4,5,6,7,8,9,10,11,12, 2, 8, 10, 3, 6, 9, 7]) == (13, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12])
 
