Very Simple and Short code for Longest Increasing Subsequence Program

Hello friends how are you , today in this blog i am going to teach, how you can write a code to find the length of longest increasing subsequence  of the given sequence(not necessarily contiguous) in which the values in the subsequence are sorted in increasing order.

I am writing this blog in December 2020 and now a days this question question is the most asked question by many companies because i have received many messages from the students about this question.

Now i am going to explain you with example

Example 1
Array: ar[] = {4, 12, 3, 15}
Output: Length of LIS is 3  which is formed by {4,12,15}

Example 2
Array: ar[] = {8,9}
Output: Length of LIS is 2  which is formed by {8,9}

Example 3
Array: ar[] = {9,8}
Output: Length of LIS is 1  which are formed by {9} and {8}

Example 4
Array: ar[] = {7, 13, 5, 17, 13, 27, 22, 32, 42}
Output: Length of LIS is 6  which is formed by {7,13,17,27,32,42}

Program for LIS

Here my programming or coding approach for this program is that , count length of Longest increasing subsequence at each element and compare it with length of LIS at previous element, if the current length of LIS is greater than previous then replace the previous length with new length and at last we get correct length of Longest increasing subsequence.

class LIS 
{
  public static void main(String[] args) 
   {
    //array initialization
    int arr[] = {7, 13, 5, 17, 13, 27, 22, 32, 42};
    //Variable declaration
    int max=0,mx,ele;
    //outer loop to access all elements of array
     for(int i=0;i<arr.length;i++)
     {
      //setting mx to 0
      mx=0;
      //passing array element to variable ele
      ele=arr[i];
      /*
      i am using this loop to count length
      of LIS at each elements of array            
      */ 
       for(int j=i;j<arr.length;j++)
       {
        /*
        this condition will execute when array 
        element will be greater               
        than current maximum element
        */
        if(ele<arr[j])
        {
        //passing the current maximum element to variable ele
         ele=arr[j];
         //incrementing the mx counter
         mx++;
         }
        }
           /*
           comparing the current length of LIS with 
           previous here if current length mx is 
           greater than previous then replace the
           value of max with mx
           */
           if(max<mx)
               max=mx; 
        }
        //printing the length of LIS
        System.out.println("Length of Longest LIS is "+(max+1));
    }
}
/*
###OUTPUT###
Length of Longest LIS is 6
*/

Here in the above program variable max is using to store maximum length of LIS and mx is using to store the current length of LIS at each element.

If you want this program in any other language then comment the programming language in comment box i will give you the code in your language.

Request:-If you found this post helpful then let me know by your comment and share it with your friend. 

 

If you want to ask a question or want to suggest then type your question or suggestion in comment box so that we could do something new for you all. 

If you have not subscribed my website then please subscribe my website. Try to learn something new and teach something new to other. 

Thanks.

Don't use my blog post without my permission.