#
Longest Decreasing Subsequence

/*********************************************************************** * Author: Isai Damier * Title: Longest Decreasing Subsequence * Project: geekviewpoint * Package: algorithms * * Statement: * Given a sequence of numbers, find a longest decreasing subsequence. * * * Time Complexity: O(n^2) * * Sample Input: {5,0,3,2,1,8} * Sample Output: {5,3,2,1} * * DEFINITION OF SUBSEQUENCE: * A sequence is a particular order in which related objects follow * each other (e.g. DNA, Fibonacci). A sub-sequence is a sequence * obtained by omitting some of the elements of a larger sequence. * * SEQUENCE SUBSEQUENCE OMISSION * {3,1,2,5,4} {1,2} 3,5,4 * {3,1,2,5,4} {3,1,4} 2,5 * * SEQUENCE NOT SUBSEQUENCE REASON * {3,1,2,5,4} {4,2,5} 4 should follow 5 * * STRATEGY: * Illustrating by finding * a longest decreasing subsequence of {5,0,3,2,1,8}: * * - Start by finding all subsequences of size 1: {5},{0},{3},{2},{1},{8}; * each element is its own decreasing subsequence. * * - Since we already have the solutions for the size 1 subsequences, * we can use them in solving for the size two subsequences. For * instance, we already know that 5 is the smallest element of a * decreasing subsequence of size 1, i.e. the subsequence {5}. * Therefore, all we need to get a subsequence of size 2 is add an * element smaller than 5 to {5}: {5,0}, {5,3}, {5,2}, {5,1}; * {3,2}, {3,1}, {2,1}. * * - Now we use the size 2 solutions to get the size 3 solutions: * {5,3,2}, {5,3,1}, {3,2,1} * * - Then we use the size 3 solutions to get the size 4 solutions: * {5,3,2,1}. Since there are no size 5 solutions, we are done. * * SUMMARY: * Instead of directly solving the big problem, we solved a smaller * version and then 'copied and pasted' the solution of the subproblem * to find the solution to the big problem. To make the 'copy and paste' * part easy, we use a table (i.e. array) to track the subproblems * and their solutions. This strategy as a whole is called Dynamic * Programming. The tabling part is known as memoization, which means * writing memo. * * To recognize whether you can use dynamic programming on a problem, * look for the following two traits: optimal substructures and * overlapping subproblems. * * Optimal Substructures: the ability to 'copy and paste' the solution * of a subproblem plus an additional trivial amount of work so to * solve a larger problem. For example, we were able to use {5,3} * itself an optimal solution to the problem {5,0,3} to get {5,3,2} * as an optimal solution to the problem {5,0,3,2}. * * Overlapping Subproblems: Okay. So in our approach the solution grew * from left to right: {5} to {5,3} to {5,3,2} etc. But in reality * we could have solved the problem using recursion trees so that * for example {5,3} could be reached either from {5} or from {3}. * That wouldn't really be a problem except we would be solving for * {5,3} more than once. Anytime a recursive solution would lead to * such overlaps, the bet is dynamic programming is the way to go. * * {5} {3} * / | \ / | \ * / | \ / | \ * / | \ / | \ * {5,0} {5,3} {5,2} {5,3} {3,2} {3,1} * * NOTE: * Dynamic Programming = Optimal Substructures + Overlapping Subproblems * Divide and Conquer = Optimal Substructures - Overlapping Subproblems * see merge sort: http://www.geekviewpoint.com/java/sorting/mergesort * * Alternate coding: Not really much difference here, just another code * that some readers will find more intuitive: * * int[] m = new int[A.length]; * Arrays.fill(m, 1); * * for(int x=1; x <A.length; x++) * for(int y = 0; y < x; y++) * if(m[y] >= m[x] && A[y] > A[x]) * m[x]++; * * int max = m[0]; * for (int i = 0; i < m.length; i++) * if (max < m[i]) * max = m[i]; * * List<Integer> result = new ArrayList<Integer>(); * for (int i = m.length-1; i >=0 ; i--) * if (max == m[i]) { * result.add(A[i]); * max--; * } * * Collections.reverse(result); * return result; * **********************************************************************/ package algorithm.programming.dynamic; import java.util.ArrayList; import java.util.List; public class LongestDecreasingSubsequence { public List<Integer> LDS(Integer[] A) { int[] m = new int[A.length]; //Arrays.fill(m, 1);//not important here for (int x = A.length - 2; x >= 0; x--) { for (int y = A.length - 1; y > x; y--) { if (m[x] <= m[y] && A[x] > A[y]) { m[x]=m[y]+1;//or use m[x]++ } } } int max = m[0]; for (int i = 0; i < m.length; i++) { if (max < m[i]) { max = m[i]; } } List<Integer> result = new ArrayList<Integer>(); for (int i = 0; i < m.length; i++) { if (max == m[i]) { result.add(A[i]); max--; } } return result; } }

package algorithm.programming.dynamic; import java.util.Arrays; import static org.junit.Assert.*; import java.util.List; import org.junit.Test; public class LongestDecreasingSubsequenceTest { @Test public void testDecreasingSubsequence() { Integer[] A = {1, 2, 3, 4, 5, 6, 7, 8, 9}; Integer[] B = {9, 8, 7, 6, 5, 4, 3, 2, 1}; Integer[] C = {15, 37, 12, 40, 8, 1, 44, 5, 3, 45, 2, 50}; Integer[] D = {15, 12, 8, 5, 3, 2}; LongestDecreasingSubsequence seq = new LongestDecreasingSubsequence(); List<Integer> actual = seq.LDS(A); assertEquals(1, actual.size()); actual = seq.LDS(B); assertTrue(Arrays.equals(B, actual.toArray(new Integer[0]))); actual = seq.LDS(C); assertTrue(Arrays.equals(D, actual.toArray(new Integer[0]))); } }