Longest Increasing Subsequence in C++

In this tutorial, we will learn about how to find the longest increasing subsequence in C++ using dynamic programming. We will also see the code implementation in C++.

We will also see examples to understand the concept in a better way.

Longest Increasing Subsequence using Dynamic Programming in C++

Let’s see on the definition, Longest increasing subsequence means to find the longest possible subsequence in which the elements are in sorted order. This subsequence is not necessarily contiguous, or unique.

Let’s see the example,

arr[]={3,4,-1,0,6,2,3};
LIS is 4.
sequence is -1,0,2,3.

Hence, in the above example, we can understand the concept of LIS.




We need to take a temporary array to store the result of size equal to arr size

int dp[n] where n is the size of arr

Now, let’s see the dynamic approach,

i=1
while i less then equal to n do
     j=0
     while j is less equal to i do
          if j<i && arr[j]<arr[i]do
              dp[i]=max(dp[i],dp[j]+1)
         else if j<i && arr[j]>arr[i] do
               j++
         else if(j==i) do
               i++ and j=0
Then find the max_element of dp[] will be LIS.

Now, let’s see the step by step update of dp[ ] array,

 dp[]={1,1,1,1,1,1,1};
i= 1 dp[]={1,2,1,1,1,1,1};
i= 2 dp[]={1,2,1,1,1,1,1};
i= 3 dp[]={1,2,1,2,1,1,1};
i= 4 dp[]={1,2,1,2,3,1,1};
i= 5 dp[]={1,2,1,2,3,3,1};
i= 6 dp[]={1,2,1,2,3,3,4};

So, by the help of the above step by step procedure, we can easily understand the dynamic approach.

Code implementation in C++

#include<bits/stdc++.h>
using namespace std;
//function to find LIS
int LIS(int arr[],int n){
   int dp[n];
      dp[0]=1;
      for(int i=1;i<n;i++){
          dp[i]=1;
          for(int j=0;j<i;j++){
              if(arr[i]>arr[j]){
                  dp[i]=max(dp[i],dp[j]+1);
              }
          }
      }
    return *max_element(dp,dp+n);	
}
int main() {
  int arr[]={3,4,-1,0,6,2,3};
  int size=sizeof(arr)/sizeof(arr[0]);
  cout<<"Longest increasing subsequence is:"<<" ";
  cout<<LIS(arr,size)<<endl;
  return 0;
}

Output

Longest increasing subsequence is: 4

You may also learn,

Solution of N-Queen problem in C++ using Backtracking

Activity Selection Problem using Greedy method in C++


Leave a Reply

Your email address will not be published. Required fields are marked *