Longest Increasing Subsequence using Dynamic Programming

«
»

This is a C++ Program that Solves Longest Increasing Subsequence Problem using Dynamic Programming technique.

Problem Description

Given a sequence of n real numbers A(1) … A(n), determine a subsequence (not necessarily contiguous) of maximum length in which the values in the subsequence form a strictly increasing sequence.

Problem Solution

This Problem can be solved using Dynamic Programming in the bottom up manner. The approach is to calculate the value of LIS for a smaller array first, memoizing it, then using this stored value to find the value of LIS for original array.

The time complexity of this solution is O(n^2).

Expected Input and Output

Case-1:

n=5
A[]={1, 4, 2, 4, 3}
Longest Increasing subsequece (LIS) = 3 formed by {1, 2, 3} or {1, 2, 4}

Case-2:

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement
 
n=9
A[]={5, 11, 3, 15, 11, 25, 20, 30, 40}
LIS=6 formed by {5, 15, 20, 30, 40}

Case-3:

 
n=15
A[]={6, 2, 10, 0, 8, 4, 12, 1, 7, 3, 11, 1, 9, 5, 13}
LIS=5 formed by {2, 4, 7, 9, 13} or { 2, 4, 7, 11, 13}

Case-4:

 
n=7
A[]={7, 1, 3, 2, 5, 4, 6}
LIS=4 formed by {1, 2, 4, 6}
Program/Source Code for Brute force solution

Here is source code of the C++ Program to Solve Longest Increasing Subsequence Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include<iostream>
  2. #include<climits>
  3. using namespace std;
  4.  
  5. //function to recursive check every possible subsequence and select the longest of all increasing
  6. //subsequences
  7. int lis_brute(int a[], int current, int n, int previous)
  8. {
  9.     //In every pass, we can either include current item or not
  10.  
  11.     //No more elements left to include in the subsequence
  12.     if(current==n)
  13.         return 0;
  14.  
  15.     //If value of current element is lesser than or equal to the previous element, we 
  16.     //cannot include it
  17.     if(a[current]<=previous)
  18.     {
  19.         return lis_brute(a,current+1,n,previous);
  20.     }
  21.  
  22.     //else once include and once don't include the current element
  23.     //and select the longest increasing subsequences out of these
  24.     return max(1+lis_brute(a,current+1,n,a[current]),lis_brute(a,current+1,n,previous));
  25. }
  26.  
  27. int main()
  28. {
  29.     int i,n;
  30.  
  31.     cout<<"Enter the no. of elements ";
  32.     cin>>n;
  33.  
  34.     int a[n];  
  35.  
  36.     cout<<"Enter the values"<<endl;
  37.     for(i=0;i<n;i++)
  38.     {
  39.         cin>>a[i];
  40.     }
  41.  
  42.     int previous=INT_MIN;
  43.     //fourth argument to keep track of value of previous element in the selected subsequence so far
  44.     //this is initialized to INT_MIN because initially there is no selected subsequence,
  45.     //so, no previous element
  46.     int result=lis_brute(a, 0, n, previous);
  47.  
  48.     cout<<"The number of terms in the longest increasing subsequence is "<<result;
  49.  
  50.     return 0;
  51. }
Program/Source Code for DP solution

Here is source code of the C++ Program to Solve Longest Increasing Subsequence Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

advertisement
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. int lis(int a[], int n)
  5. { 
  6.     int i, j;
  7.  
  8.     //create an array b of size n ie, b[n]
  9.     //b[i] represents the value of longest increasing subsequence with a[i] being the last element
  10.  
  11.     //b[i]=longest increasing subsequence for the array a[0...i] by including a[i] in the subseuence
  12.     //at the end
  13.  
  14.     int b[n];
  15.  
  16.     //Since, we are definitely including a[i] for the calculation of b[i], b[i] will 
  17.     //either be equal to 1 or greater than 1
  18.     //so, initialize b
  19.     for(i=0;i<n;i++)
  20.         b[i]=1;
  21.  
  22.  
  23.     //now, we have to fill this b array
  24.  
  25.     //we will calulate the value of b[i] for every 1<=i<=n by checking whether any subsequence
  26.     //b[0], b[1],...,b[i-1] can fit before a[i] and then selecting the maximum out of them
  27.     for(i=1;i<n;i++)
  28.     {
  29.         //for every i, we will check all values of 0<=j<i for subsequences b[j] to which a[i]
  30.         //could be appended and select the longest one
  31.         for(j=0;j<i;j++)
  32.         {
  33.             //if the current element ie, the ith element has value greater than jth element, that
  34.             //means a[i] can be appended after b[j]
  35.             //Since, we are interested in finding the longest of such subsequences, we will consider
  36.             //only those values of b[j] that are greater than or equal to b[i]
  37.             if(a[i]>a[j] && b[i]<b[j]+1)
  38.             {
  39.                 b[i]=b[j]+1;
  40.             }
  41.         }
  42.     }
  43.  
  44.     //now, we have calculated all the values of b[i] for 0<=i<n
  45.     //The length of the longest increasing subsequence of the given array is the maximum of all
  46.     //these values because the longest increasing subsequence can end with any element of the array
  47.  
  48.     //finding maximum element in b array
  49.     int max=0;
  50.  
  51.     for(i=0;i<n;i++)
  52.     {
  53.         if(b[i]>max)
  54.             max=b[i];
  55.     }
  56.  
  57.     return max;
  58.  
  59.  
  60. }
  61.  
  62. int main()
  63. {
  64.     int i,n;
  65.  
  66.     cout<<"Enter the no. of elements ";
  67.     cin>>n;
  68.  
  69.     int a[n];  
  70.  
  71.     cout<<"Enter the values"<<endl;
  72.     for(i=0;i<n;i++)
  73.     {
  74.         cin>>a[i];
  75.     }
  76.  
  77.     int result=lis(a,n);
  78.  
  79.     cout<<"The number of terms in the longest increasing subsequence is "<<result;
  80.  
  81.     return 0;
  82. }
Program Explanation

In the main function, we ask the user to input the elments of the array. We pass this array to the function lis as parameter. This function will calculate the expected result and return it. The returned value will be displayed.

Runtime Test Cases
 
Case-1:
$ g++ lis.cpp
$ ./a.out
Enter the no. of elements 5
Enter the values
1
4
2
4
3
The number of terms in the longest increasing subsequence is 3

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.

advertisement

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.