#
Longest Increasing Subsequence

/*********************************************************************** * Author: Isai Damier * Title: Longest Increasing Subsequence * Project: geekviewpoint * Package: algorithms * * Statement: * Given a sequence of numbers, find a longest increasing subsequence. * * * Time Complexity: O(n^2) * * Sample Input: {8,1,2,3,0,5} * Sample Output: {1,2,3,5} * * 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 increasing subsequence * of {8,1,2,3,0,5}: * * - Start by finding all subsequences of size 1: {8},{1},{2},{3},{0},{5}; * each element is its own increasing 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 0 is the smallest element of an * increasing subsequence of size 1, i.e. the subsequence {0}. * Therefore, all we need to get a subsequence of size 2 is add an * element greater than 0 to {0}: {0,5}. The other size 2 * subsequences are: {1,2}, {1,3}, {1,5}, {2,3}, {2,5}, {3,5}. * * - Now we use the size 2 subsequences to get the size 3 subsequences: * {1,2,3}, {1,2,5}, {1,3,5}, {2,3,5} * * - Then we use the size 3 subsequences to get the size 4 subsequences: * {1,2,3,5}. 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 {1,2} * itself an optimal solution to the problem {8,1,2} to get {1,2,3} * as an optimal solution to the problem {8,1,2,3}. * * Overlapping Subproblems: Okay. So in our approach the solution grew * from left to right: {1} to {1,2} to {1,2,3} etc. But in reality * we could have solved the problem using recursion trees so that * for example {1,2} could be reached either from {1} or from {2}. * That wouldn't really be a problem except we would be solving for * {1,2} more than once. Anytime a recursive solution would lead to * such overlaps, the bet is dynamic programming is the way to go. * * {1} {2} * / | \ / | \ * / | \ / | \ * / | \ / | \ * {1,2} {1,3} {1,5} {1,2} {2,3} {2,5} * * 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 LongestIncreasingSubsequence { public Integer[] LIS(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 (A[x] < A[y] && m[x] <= m[y]) { m[x]++;//or use m[x] = m[y] + 1; } } } int max = m[0]; for (int i = 1; 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 (m[i] == max) { result.add(A[i]); max--; } } return result.toArray(new Integer[0]); } }

package algorithm.programming.dynamic; import java.util.Arrays; import static org.junit.Assert.*; import org.junit.After; import org.junit.Before; import org.junit.Test; public class LongestIncreasingSubsequenceTest { LongestIncreasingSubsequence seq; @Before public void setUp() throws Exception { seq = new LongestIncreasingSubsequence(); } @After public void tearDown() throws Exception { seq = null; } @Test public void testLIS() { Integer[] A = {1, 2, 3, 4, 5, 6, 7, 8, 9}; Integer[] B = {9, 8, 7, 6, 5, 4, 3, 2, 1}; Integer[] C = {50, 2, 45, 3, 5, 44, 1, 8, 40, 12, 37, 15}; Integer[] D = {2, 3, 5, 8, 12, 37}; Integer[] actual = seq.LIS(A); assertTrue(Arrays.equals(A, actual)); assertEquals(1, seq.LIS(B).length); actual = seq.LIS(C); assertTrue(Arrays.equals(D, actual)); } }