Introduction
In this article, we will talk about the longest increasing subsequence problem. It is a trivial problem with solutions ranging from exponential complexity to logarithmic complexity.
Problems like longest increasing subsequence are asked in many coding competitions and coding interviews, directly or indirectly. Other than this, the longest increasing subsequence is also used in various places like:
- Git- for their version control system.
-
MUMmer system- for aligning entire genomes.
This article requires some prior knowledge of Dynamic Programming. Readers with no previous knowledge of this paradigm can read this article: Dynamic Programming & algorithms.
I hope many of you readers are now excited to learn about the Longest Increasing Subsequence. So without any further ado, let’s start our journey.
Problem Statement
For a given array with N elements, you need to find the length of the longest subsequence from the array such that all the elements of the subsequence are sorted in strictly increasing order.
A strictly Increasing Sequence is when each term in the sequence is larger than the preceding term.
Sample Input :
6
5 4 11 1 16 8
Sample Output :
3
Explanation:
Length of longest subsequence is 3 i.e. [5, 11, 16] or [4, 11, 16].
The increasing subsequence can start from any point and end at any point. It is also not certain that the first increasing subsequence which we have found is the longest. Thus we have to compute all the possible increasing subsequences and then find the longest among them.
For the ease of the readers this article is a two-part article. This is the first part of the article, which contains the iterative solution and a semi-optimized solution obtained by using DP. The second part of the article can be found here. Reading both articles will help you build up an efficient solution on your own in no time.
It is recommended to first practice the Longest Increasing Subsequence on Coding Ninjas Studio before proceeding to the solution.
Without further ado, let’s get started.
Approach 1 - Recursion
Consider the array A as {5,4,11,1,15,8}.
Consider a variable prev and a variable idx. For every element in A, we have two choices: either it is part of the LIS, or it is not.
Now is it always like it will have an option of being a part of LIS? The answer is NO because it can only be part of the LIS if and only if the previous element included in LIS is smaller than A[idx].
In our code, we have a function called LIS which will return the length of the longest increasing subsequence and will take three parameters as follows:
- idx: To store the index of the current element to be included or excluded.
- prev: To store the previously included element in LIS. Initially, we will pass it as the minimum value of an integer.
- Array A: The input array
C++ Implementation of Approach 1
|
#include <iostream> #include <vector> using namespace std; int LIS(int input[], int idx, int prev, int size){ if(idx == size) return 0; // to store maximum length int max = 0 ; // include if(input[idx] > prev){ /* * if input[idx] > prev, then it can become the part of LIS * if it is getting included then we need to increase the length by 1 */ int len1 = 1 + LIS(input, idx+1, input[idx], size); max = max > len1 ? max : len1; } // exclude: prev obtained till now will be the next prev int len2 = LIS(input, idx+1, prev, size); max = max > len2 ? max : len2; return max; } //main function int main() { int input[] = {3, 4, -1, 0, 6, 2, 3}; //input array int size = sizeof(input) / sizeof(input[0]); //size of input array cout << "The length of the longest increasing subsequence is: " << LIS(input, 0, INT32_MIN, size); return 0; } |
OUTPUT
| The length of the longest increasing subsequence is: 4 |
Complexity Analysis
Time Complexity
In the code mentioned above, for every idx we have two possible options, either include or exclude the element in our LIS. Thus time complexity is:
T(n) = O(2n),
where n is the size of the input array.
Space Complexity
In the code mentioned above, we use recursion to find the LIS of the given input array. Thus,
Space Complexity = O(n),
where n is the space occupied by the recursion stack.
In the worst case, we have n functions in the recursion stack occupying O(n) memory.
The recursion tree obtained by this recursive approach is:
We can see that the highlighted functions are being called multiple times. These redundant calculations drastically affect our time complexity. So, to avoid these redundant computations, we use the concept of Dynamic Programming. To know how to apply dynamic programming to this problem, let’s proceed to our following approach.
133+ registered 
