DP: Longest Increasing Sub-Sequence

Problem Statement:
        Given a sequence , find the Longest sub-sequence which is increasing.
        Given Sequence: 

                      2 , 7 , 3 , 4 , 9 , 8 , 12

Resultant Longest sub-sequence is 2 , 3 , 4 , 9 , 12

Solution:

Full Source Code: LINK

  What are the number of possbile subsets ?
 = 2^n

We will solve this problem using Dynamic Programming(DP)
For a DP , it has the properties
1. Optimal Sub-Structure
          It means if i have solution of sub- problems , and optimal solution of those sub-problems can be combined to get the solution of bigger problem..

We will define a term ,
L(i) = Length of the  Longest Increasing Sub-Sequence which includes element arr[i] as its last element.

Equation for the optimal sub-structure
      L(i) = 1 + MAX ( L(j) )    , where 0<= j < i  and A[i]  > A[j]
  
2. Overlapping Sub-Problem:
              We can observe that there are values which needs to be recomputed again and again, therefore its and overlapping.

Consider and example
           

      
As i have discussed in previous posts of DP(Dynamic Programming) can be solved by memomisation or tabulation method,
I have used tabulation method here to find the solution

Intermediate Steps involved for the given sample

 L(0) = 1   
 L(1) = 1 + Max(L(0))  
     = 1 + Max(1)  
     = 1 + 1  
     = 2  
 L(2) = 1 + Max(L(0))  
     = 1 + Max(1)  
     = 2  
 L(3) = 1 + Max(L(0),L(2))  
     = 1 + Max(1 ,2)  
     = 1 + 2   
     = 3  
 L(4) = 1 + Max(L(0),L(1),L(2),L(3))       
     = 1 + Max(1 , 2 , 2 , 3)  
     = 1 + 3  
     = 4  
 L(5) = 1 + Max(L(0),L(1),L(2),L(3))  
     = 1 + Max(1 , 2 , 2 , 3 )  
     = 4  
 L(6) = 1 + Max(L(0),L(1),L(2),L(3),L(4),L(5))  
     = 1 + Max(1 , 2 , 2 , 3 , 4 , 4)  
     = 5  

Below is the logic of the sub-routine to find the increasing sub sequence:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

private static int[] LIS; private static int[] sol; //Array to retrive the sequence static int tail=0; //final element of sequence /** * Procedure to find LIS * @param arr : input array * @return longest value on increasing sub sequence */ public static int lis(int[] arr){ int len = arr.length ; LIS = new int[len]; sol = new int[len] ; Arrays.fill(sol, -1); LIS[0] = 1; //base case int MAX_LIS=1; // default value int max; // gets max value for each i for(int i=1;i < len ; i++) { max=0; for(int j=0 ; j<i ; j++) { if(arr[i] > arr[j] && LIS[j] > max ) { sol[i] = j ; //used to save max = LIS[j]; //update max for value of i } } LIS[i] = 1 + max ; if(LIS[i] > MAX_LIS){ MAX_LIS = LIS[i]; tail=i; } } printSequence(sol, arr); System.out.println("Sequence length : " + MAX_LIS); return MAX_LIS ; }

Below is the sub-routine to print the increasing sub-sequence computed from the above sub routine.

1 2 3 4 5

public static void printSequence(int[] sol , int[] arr){ System.out.println("Sequence : "); for (int j = tail; j >= 0; j = sol[j]) System.out.print(arr[j]+"\t"); }

Please comment and post suggestions , for the above code.

Happy Coding !! :)