# Longest V-Shaped Subsequenceby Isai Damier, Android Engineer @ Google

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