#
Longest V-Shaped Subsequence

#======================================================================= # Author: Isai Damier # Title: Longest V-Shaped Subsequence # Project: geekviewpoint # Package: algorithms # # Statement: # Given a sequence of numbers, find a longest v-shaped subsequence. # # Time Complexity: O(n^2) # # Sample Input: {50, 1, 57, 2, 3, 17, 4, 11, 5, 6} # Sample Output: {50, 1, 2, 3, 4, 5, 6} # # STRATEGY: # # This longest v-shaped subsequence problem is the combination of the # longest decreasing subsequence problem with the longest increasing # subsequence problem. Hence, we strongly recommend that you read on # those two programs before continuing. Their respective links are: # http://www.geekviewpoint.com/python/dynamic_programming/lds and # http://www.geekviewpoint.com/python/dynamic_programming/lis. # # ... waiting ... waiting ... waiting ... waiting ... waiting ... # # Okay. Now that you understand LIS and LDS, here is how to solve the # longest v-shaped sequence (LVS) problem. # # - Use an array to memoize the decreasing subsequences. Call it D # - Use an array to memoize the increasing subsequences. Call it U # - Whereas every subsequence d in D is decreasing (i.e. going down); # whereas every subsequence u in U is increasing; any intersection # between d and u must result in a v-shaped sequence. Therefore, # find the intersection x between some d in D and some u in U # such that the length of u+d is maximal. # - Prthe actual sequence using the fact that d ends at x and u # starts at x. #======================================================================= def longestVSequence( A ): d = memoizeDecreasingSubsequences( A ) u = memoizeIncreasingSubsequences( A ) n = findVertexOfLongestVSubsequence( A, u, d ) # point where \ meets / if n == -1: return None # no V-shape found result = [] loadDecreasingHalfOfV( A, d, n, result ) loadIncreasingHalfOfV( A, u, n, result ) return result def memoizeDecreasingSubsequences( A ): d = [1] * len( A ) for x in range( len( A ) ): for y in range( x ): if A[x] < A[y] and d[x] <= d[y]: d[x] = 1 + d[y] return d def memoizeIncreasingSubsequences( A ) : u = [1] * len( A ) for x in range( len( A ) - 2, -1, -1 ): for y in range( len( A ) - 1 , x, -1 ): if A[x] < A[y] and u[x] <= u[y]: u[x] = 1 + u[y] return u def findVertexOfLongestVSubsequence( A, u, d ): max_value = 0 n = -1 for x in range( len( A ) ): if d[x] > 1 and u[x] > 1 and d[x] + u[x] > max_value: max_value = d[x] + u[x] n = x return n def loadDecreasingHalfOfV( A, d, n, result ) : mag = d[n] - 1 for x in range( n, -1, -1 ): if mag == d[x]: result.append( A[x] ) mag -= 1 result.reverse() def loadIncreasingHalfOfV( A, u, n, result ): mag = u[n] for x in range( n, len( A ) ) : if mag == u[x]: result.append( A[x] ) mag -= 1

import unittest from dynamic_programming import LongestVSequence as v_seq class Test( unittest.TestCase ): def testLongestVSequence( self ): up = [1, 2, 3, 4, 5, 6, 7, 8, 9] down = [9, 8, 7, 6, 5, 4, 3, 2, 1] self.assertIsNone( v_seq.longestVSequence( up ) ) self.assertIsNone( v_seq.longestVSequence( down ) ) mirror = [0, 6, 1, 5, 25, 4, 33, 3, 2, 1, 40, 2, 3, 17, 4, 11, 5, 6] expMirror = [6, 5, 4, 3, 2, 1, 2, 3, 4, 5, 6] self.assertEquals( expMirror, v_seq.longestVSequence( mirror ) ) checkMark = [50, 1, 57, 2, 3, 17, 4, 11, 5, 6] expChkMark = [50, 1, 2, 3, 4, 5, 6] self.assertEquals( expChkMark, v_seq.longestVSequence( checkMark ) ) reverseCheck = [6, 5, 11, 4, 18, 3, 2, 1, 50] expRevChk = [6, 5, 4, 3, 2, 1, 50] self.assertEquals( expRevChk, v_seq.longestVSequence( reverseCheck ) ) v = [6, 57, 5, 13, 7, 69, 4, 17, 36, 3, 38, 2, 40, 1, 50] expectedV = [57, 13, 7, 4, 17, 36, 38, 40, 50] self.assertEquals( expectedV, v_seq.longestVSequence( v ) )