#
Longest Decreasing Subsequence

#======================================================================= # Author: Isai Damier # Title: Longest Decreasing Subsequence # Project: geekviewpoint # Package: algorithms # # Statement: # Given a sequence of numbers, find a longest decreasing subsequence. # # # Time Complexity: O(n^2) # # Sample Input: [5,0,3,2,1,8] # Sample Output: [5,3,2,1] # # DEFINITION OF SUBSEQUENCE: # A sequence is a particular order in which related objects follow # each other (e.g. DNA, Fibonacci). A sub-sequence is a sequence # obtained by omitting some of the elements of a larger sequence. # # SEQUENCE SUBSEQUENCE OMISSION # [3,1,2,5,4] [1,2] 3,5,4 # [3,1,2,5,4] [3,1,5] 2,4 # # SEQUENCE NOT SUBSEQUENCE REASON # [3,1,2,5,4] [4,2,5] 4 should follow 5 # # STRATEGY: # Illustrating by finding # a longest decreasing subsequence of [5,0,3,2,1,8]: # # - Start by finding all subsequences of size 1: [5],[0],[3],[2],[1],[8]; # each element is its own decreasing subsequence. # # - Since we already have the solutions for the size 1 subsequences, # we can use them in solving for the size two subsequences. For # instance, we already know that 5 is the smallest element of a # decreasing subsequence of size 1, i.e. the subsequence [5]. # Therefore, all we need to get a subsequence of size 2 is add an # element smaller than 5 to [5]: [5,0], [5,3], [5,2], [5,1]; # [3,2], [3,1], [2,1]. # # - Now we use the size 2 solutions to get the size 3 solutions: # [5,3,2], [5,3,1], [3,2,1] # # - Then we use the size 3 solutions to get the size 4 solutions: # [5,3,2,1]. Since there are no size 5 solutions, we are done. # # SUMMARY: # Instead of directly solving the big problem, we solved a smaller # version and then 'copied and pasted' the solution of the subproblem # to find the solution to the big problem. To make the 'copy and paste' # part easy, we use a table (i.e. list) to track the subproblems # and their solutions. This strategy as a whole is called Dynamic # Programming. The tabling part is known as memoization, which means # writing memo. # # To recognize whether you can use dynamic programming on a problem, # look for the following two traits: optimal substructures and # overlapping subproblems. # # Optimal Substructures: the ability to 'copy and paste' the solution # of a subproblem plus an additional trivial amount of work so to # solve a larger problem. For example, we were able to use [5,3] # itself an optimal solution to the problem [5,0,3] to get [5,3,2] # as an optimal solution to the problem [5,0,3,2]. # # Overlapping Subproblems: Okay. So in our approach the solution grew # from left to right: [5] to [5,3] to [5,3,2] etc. But in reality # we could have solved the problem using recursion trees so that # for example [5,3] could be reached either from [5] or from [3]. # That wouldn't really be a problem except we would be solving for # [5,3] more than once. Any time a recursive solution would lead to # such overlaps, the bet is dynamic programming is the way to go. # # [5] [3] # / | \ / | \ # / | \ / | \ # / | \ / | \ # [5,0] [5,3] [5,2] [5,3] [3,2] [3,1] # # NOTE: # Dynamic Programming = Optimal Substructures + Overlapping Subproblems # Divide and Conquer = Optimal Substructures - Overlapping Subproblems # see merge sort: http://www.geekviewpoint.com/python/sorting/mergesort # # Alternate coding: Not really much difference here, just another code # that some readers will find more intuitive: # # m = [1] * len( A ) # # for x in range(len(A)): # for y in range(x): # if m[y] >= m[x] and A[y] > A[x]: # m[x]+=1 # # max_value = max(m) # # result = [] # for i in range(m-1,-1,-1): # if max == m[i]: # result.append(A[i]) # max-=1 # # result.reverse() # return result #======================================================================= def LDS( A ): m = [0] * len( A ) # starting with m = [1] * len( A ) is not necessary for x in range( len( A ) - 2, -1, -1 ): for y in range( len( A ) - 1, x, -1 ): if m[x] <= m[y] and A[x] > A[y]: m[x] = m[y] + 1 # or use m[x]+=1 #=================================================================== # Use the following snippet or the one line below to get max_value # max_value=m[0] # for i in range(m): # if max_value < m[i]: # max_value = m[i] #=================================================================== max_value = max( m ) result = [] for i in range( len( m ) ): if max_value == m[i]: result.append( A[i] ) max_value -= 1 return result

import unittest from dynamic_programming import LongestDecreasingSubsequence as subsequence class Test( unittest.TestCase ): def testDecreasingSubsequence( self ): A = [1, 2, 3, 4, 5, 6, 7, 8, 9] B = [9, 8, 7, 6, 5, 4, 3, 2, 1] C = [15, 37, 12, 40, 8, 1, 44, 5, 3, 45, 2, 50] D = [15, 12, 8, 5, 3, 2] actual = subsequence.LDS( A ) self.assertEquals( 1, len( actual ) ) actual = subsequence.LDS( B ) self.assertEquals( B, actual ) actual = subsequence.LDS( C ) self.assertEquals( D, actual )