Tuesday, 2 January 2018

C++ Program to Find Longest Increasing Subsequence

LIS (Longest Increasing Subsequence) problem is used to find the longest subsequence of array which is in sorted order. C++ Program for finding the longest increasing subsequence is given below.

Example:

Let A[]= {10, 22, 9, 33, 21, 50, 41, 60, 80} 

Length of Longest Increase subsequence is 6 and LIS is {10, 22, 33, 50, 60, 80}.

PROGRAM:


#include <bits/stdc++.h>
using namespace std;

int calculate(const vector<int> &A)
{
      if(A.size()==0) return 0;
      
      int n=A.size();
      
      int list[n];
      for(int i=0;i<n;i++) list[i]=1;
      for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                  if(A[j]<A[i]){
                        list[i]=max(list[i],list[j]+1);
                  }
            }
      }
      
      int result=0;
      for(int i=0;i<n;i++){
           if(result<list[i]){
                result=list[i];
           }
      }
      return result;

}
int main(){
    
    
      int n;

      cout<<"\nEnter the total number of elements: \n";
      cin>>n;

      cout<<"\nEnter the elements of array:\n";
      int num;

      std::vector<int> A;

      for(int i=0;i<n;i++){
           cin>>num;
           A.push_back(num);
      }
     
      int result=calculate(A);
      cout<<"\nThe length of longest increasing subsequence is: "<<result<<"\n";
      return 0;
}

OUTPUT:





EmoticonEmoticon