#=======================================================================
# 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 ) )
