Longest Increasing Subsequence Problem

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:

 
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:

Note: Join free Sanfoundry classes at Telegram or Youtube

 
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.

```
#include<iostream>
```
```
#include<climits>
```
```
using namespace std;
```
```
 
```

//function to recursive check every possible subsequence and select the longest of all increasing

```
//subsequences
```

int lis_brute(int a[], int current, int n, int previous)

```
{
```

    //In every pass, we can either include current item or not

```
 
```

    //No more elements left to include in the subsequence

```
    if(current==n)
```
```
        return 0;
```
```
 
```

    //If value of current element is lesser than or equal to the previous element, we

```
    //cannot include it
```
```
    if(a[current]<=previous)
```
```
    {
```

        return lis_brute(a,current+1,n,previous);

```
    }
```
```
 
```

    //else once include and once don't include the current element

    //and select the longest increasing subsequences out of these

    return max(1+lis_brute(a,current+1,n,a[current]),lis_brute(a,current+1,n,previous));

```
}
```
```
 
```
```
int main()
```
```
{
```
```
    int i,n;
```
```
 
```
```
    cout<<"Enter the no. of elements ";
```
```
    cin>>n;
```
```
 
```
```
    int a[n];  
```
```
 
```
```
    cout<<"Enter the values"<<endl;
```
```
    for(i=0;i<n;i++)
```
```
    {
```
```
        cin>>a[i];
```
```
    }
```
```
 
```
```
    int previous=INT_MIN;
```

    //fourth argument to keep track of value of previous element in the selected subsequence so far

    //this is initialized to INT_MIN because initially there is no selected subsequence,

```
    //so, no previous element
```

    int result=lis_brute(a, 0, n, previous);

```
 
```

    cout<<"The number of terms in the longest increasing subsequence is "<<result;

```
 
```
```
    return 0;
```
```
}
```

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.

```
#include<iostream>
```
```
using namespace std;
```
```
 
```
```
int lis(int a[], int n)
```
```
{ 
```
```
    int i, j;
```
```
 
```

    //create an array b of size n ie, b[n]

    //b[i] represents the value of longest increasing subsequence with a[i] being the last element

```
 
```

    //b[i]=longest increasing subsequence for the array a[0...i] by including a[i] in the subseuence

```
    //at the end
```
```
 
```
```
    int b[n];
```
```
 
```

    //Since, we are definitely including a[i] for the calculation of b[i], b[i] will

    //either be equal to 1 or greater than 1

```
    //so, initialize b
```
```
    for(i=0;i<n;i++)
```
```
        b[i]=1;
```
```
 
```
```
 
```
```
    //now, we have to fill this b array
```
```
 
```

    //we will calulate the value of b[i] for every 1<=i<=n by checking whether any subsequence

    //b[0], b[1],...,b[i-1] can fit before a[i] and then selecting the maximum out of them

```
    for(i=1;i<n;i++)
```
```
    {
```

        //for every i, we will check all values of 0<=j<i for subsequences b[j] to which a[i]

        //could be appended and select the longest one

```
        for(j=0;j<i;j++)
```
```
        {
```

            //if the current element ie, the ith element has value greater than jth element, that

            //means a[i] can be appended after b[j]

            //Since, we are interested in finding the longest of such subsequences, we will consider

            //only those values of b[j] that are greater than or equal to b[i]

            if(a[i]>a[j] && b[i]<b[j]+1)

```
            {
```
```
                b[i]=b[j]+1;
```
```
            }
```
```
        }
```
```
    }
```
```
 
```

    //now, we have calculated all the values of b[i] for 0<=i<n

    //The length of the longest increasing subsequence of the given array is the maximum of all

    //these values because the longest increasing subsequence can end with any element of the array

```
 
```

    //finding maximum element in b array

```
    int max=0;
```
```
 
```
```
    for(i=0;i<n;i++)
```
```
    {
```
```
        if(b[i]>max)
```
```
            max=b[i];
```
```
    }
```
```
 
```
```
    return max;
```
```
 
```
```
 
```
```
}
```
```
 
```
```
int main()
```
```
{
```
```
    int i,n;
```
```
 
```
```
    cout<<"Enter the no. of elements ";
```
```
    cin>>n;
```
```
 
```
```
    int a[n];  
```
```
 
```
```
    cout<<"Enter the values"<<endl;
```
```
    for(i=0;i<n;i++)
```
```
    {
```
```
        cin>>a[i];
```
```
    }
```
```
 
```
```
    int result=lis(a,n);
```
```
 
```

    cout<<"The number of terms in the longest increasing subsequence is "<<result;

```
 
```
```
    return 0;
```
```
}
```

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.

If you find any mistake above, kindly email to [email protected]

« Prev - Making Change Problem using Dynamic Programming

» Next - Box Stacking Problem using Dynamic Programming

Related Posts:

Recommended Articles: