Coders Packet

Finding Longest Increasing Subsequence using C++ and Dynamic Programming

By G Ganga Jathin

Here we find the length of the Longest Increasing Subsequence(LIS) using C++ Language and by Dynamic Programming

This packet Helps in solving to find the length of the Longest Increasing Subsequence(LIS) for the given array.

The Longest Increasing Subsequence of the given array means the longest subsequence of the array which is increasing.
For example consider the array { 5, 2, 10, 7, 4, 12}:- Here the length of the LIS for the given array would be  3.
Its corresponding subsequence can be {5, 10,12} or {2, 10, 12}.

So here we use another array where it stores the length of the longest increasing subsequence at every index. Initially, the longest increasing subsequence at every index would be 1.
Then we iterate using two index pointers i and j, here j iterates over the array till the current index and finds total subsequence and updates length of LIS at the current index.

Implementation of the LIS:- 

for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < i;j++)
        {
            if(arr[j] < arr[i])lis[i] = max(lis[i],lis[j]+1);
        }
        maxi = max(maxi,lis[i]);
    }

here the maxi variable contains the maximum length of Longest Increasing Subsequence

 


In this way, we store the longest increasing subsequence at every index and print out the LIS at the last index as the final answer.

In this array, the longest increasing subsequence we used is the main principle of Dynamic Programming applied here.

 

 

Usage:- 

Download the project and extract it to the desired folder

Open the source code in the C++ IDE of your choice

Run it and input the size of the array and its elements to get the required length of the LIS of the given array.

Download project

Reviews Report

Submitted by G Ganga Jathin (GangaJathin)

Download packets of source code on Coders Packet