25 Nov 2013

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 !! :)

No comments:

Post a Comment