Longest V-Shaped Subsequence
by Isai Damier

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