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/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>();
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]) {
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]) {
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));
}
}```