Longest subsequence of Array.

The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. For example, the length of LIS for {10, 22, 9, 33, 21, 50, 41, 60, 80} is 6 and LIS is {10, 22, 33, 50, 60, 80}.

                       Program

import java.util.Scanner;
public class LongestIncreasingSubsequence {

   /** function lis **/
 public   int[] lis(int[] X)
   {        
       int n = X.length - 1;
       int[] M = new int[n + 1];  
       int[] P = new int[n + 1]; 
       int L = 0;
 
       for (int i = 1; i < n + 1; i++)
       {
           int j = 0;
 
                     for (int pos = L ; pos >= 1; pos--)
           {
               if (X[M[pos]] < X[i])
               {
                   j = pos;
                   break;
               }
           }            
           P[i] = M[j];
           if (j == L || X[i] < X[M[j + 1]])
           {
               M[j + 1] = i;
               L = Math.max(L,j + 1);
           }
       }
 
       /** backtrack **/
 
       int[] result = new int[L];
       int pos = M[L];
       for (int i = L - 1; i >= 0; i--)
       {
           result[i] = X[pos];
           pos = P[pos];
       }
       return result;             
   }
 
   /** Main Function **/
   public static void main(String[] args) 
   {    
       Scanner scan = new Scanner(System.in);
       System.out.println("Longest Increasing Subsequence Algorithm Test\n");
 
       System.out.println("Enter number of elements");
       int n = scan.nextInt();
       int[] arr = new int[n + 1];
       System.out.println("\nEnter "+ n +" elements");
       for (int i = 1; i <= n; i++)
           arr[i] = scan.nextInt();
 
       LongestIncreasingSubsequence obj = new LongestIncreasingSubsequence(); 
       int[] result = obj.lis(arr);       
 
       /** print result **/ 
 
       System.out.print("\nLongest Increasing Subsequence : ");
       for (int i = 0; i < result.length; i++)
           System.out.print(result[i] +" ");
       System.out.println();
   }
}