/***********************************************************************
* 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));
}
}