Longest V-Shaped Subsequence
by 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/java/dynamic_programming/lds and
 *  http://www.geekviewpoint.com/java/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.
 *  - Print the actual sequence using the fact that d ends at x and u
 *    starts at x.
 *    
 **********************************************************************/ 
 package algorithm.programming.dynamic;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class LongestVSequence {

  public Integer[] longestVSequence(Integer[] A) {
    int[] d = new int[A.length];
    int[] u = new int[A.length];
    memoizeDecreasingSubsequences(A, d);
    memoizeIncreasingSubsequences(A, u);
    int n = findVertexOfLongestVSubsequence(A, u, d);//point where \ meets /	
    if (n == -1) {
      return null;// no V-shape found
    }
    List<Integer> result = new ArrayList<Integer>();
    loadDecreasingHalfOfV(A, d, n, result);
    loadIncreasingHalfOfV(A, u, n, result);
    return result.toArray(new Integer[0]);
  }//longestVSequence

  private void memoizeDecreasingSubsequences(Integer[] A, int[] d) {
    Arrays.fill(d, 1);
    for (int x = 0; x < A.length; x++) {
      for (int y = 0; y < x; y++) {
        if (A[x] < A[y] && d[x] <= d[y]) {
          d[x] = 1 + d[y];
        }
      }
    }
  }

  private void memoizeIncreasingSubsequences(Integer[] A, int[] u) {
    Arrays.fill(u, 1);
    for (int x = A.length - 2; x >= 0; x--) {
      for (int y = A.length - 1; y > x; y--) {
        if (A[x] < A[y] && u[x] <= u[y]) {
          u[x] = 1 + u[y];
        }
      }
    }
  }

  private int findVertexOfLongestVSubsequence(Integer[] A, int[] u, int[] d) {
    int max = 0, n = -1;
    for (int x = 0; x < A.length; x++) {
      if (d[x] > 1 && u[x] > 1 && d[x] + u[x] > max) {
        max = d[x] + u[x];
        n = x;
      }
    }
    return n;
  }

  private void loadDecreasingHalfOfV(Integer[] A, int[] d, int n,
          List<Integer> result) {
    for (int x = n, mag = d[n] - 1; x >= 0; x--) {
      if (mag == d[x]) {
        result.add(A[x]);
        mag--;
      }
    }
    Collections.reverse(result);
  }

  private void loadIncreasingHalfOfV(Integer[] A, int[] u, int n,
          List<Integer> result) {
    for (int x = n, mag = u[n]; x < A.length; x++) {
      if (mag == u[x]) {
        result.add(A[x]);
        mag--;
      }
    }
  }
}//class LongestVSequence
package algorithm.programming.dynamic;

import static org.junit.Assert.*;

import org.junit.After;
import org.junit.Before;
import org.junit.Test;

public class LongestVSequenceTest {

  LongestVSequence seq;

  @Before
  public void setUp() throws Exception {
    seq = new LongestVSequence();
  }

  @After
  public void tearDown() throws Exception {
    seq = null;
  }

  @Test
  public void testLongestVSequence() {
    Integer[] up = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    Integer[] down = {9, 8, 7, 6, 5, 4, 3, 2, 1};
    assertNull(seq.longestVSequence(up));
    assertNull(seq.longestVSequence(down));

    Integer[] mirror = {0, 6, 1, 5, 25, 4, 33, 3, 2, 1, 40, 2, 3, 17, 4, 11, 5, 6};
    Integer[] expectedMirror = {6, 5, 4, 3, 2, 1, 2, 3, 4, 5, 6};
    assertArrayEquals(expectedMirror, seq.longestVSequence(mirror));

    Integer[] checkMark = {50, 1, 57, 2, 3, 17, 4, 11, 5, 6};
    Integer[] expectedCheckMark = {50, 1, 2, 3, 4, 5, 6};
    assertArrayEquals(expectedCheckMark, seq.longestVSequence(checkMark));

    Integer[] reverseCheck = {6, 5, 11, 4, 17, 3, 2, 1, 50};
    Integer[] expectedReverseCheck = {6, 5, 4, 3, 2, 1, 50};
    assertArrayEquals(expectedReverseCheck, seq.longestVSequence(reverseCheck));

    Integer[] v = {6, 57, 5, 13, 7, 69, 4, 17, 36, 3, 38, 2, 40, 1, 50};
    Integer[] expectedV = {57, 13, 7, 4, 17, 36, 38, 40, 50};
    assertArrayEquals(expectedV, seq.longestVSequence(v));
  }
}