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