In dynamic programming, a problem may be broken down into smaller subproblems and solved more efficiently, since the optimum solution to the core problem is dependent on the optimal solution to each of the smaller subproblems. Richard Bellman came up with the idea for the method back in the '50s. The DP method only computes the answer to each subproblem once and then remembers it, saving time by not recomputing it for subsequent appearances of the same subproblem.
By the end of this tutorial, you will better understand the recursive and dynamic programming approach to find the Longest Increasing Subsequence with the necessary details and practical implementations.
Problem Statement for the Longest Increasing Subsequence Problem
The Longest increasing subsequence (LIS) problem involves finding the length of the longest increasing subsequence inside a given sequence. All items within it are sorted in ascending order of increasing length. As an example, the length of LIS for the set {10, 15, 13, 9, 21, 22, 35, 29, 64} is 6 and LIS is the set {10, 15, 21, 22, 35, 64}.
Now, look at the recursive solution to solve the Longest increasing subsequence.
Recursion-Based Solution to Find the Longest Increasing Subsequence
This recursive approach is more of a brute force approach. You will follow the below steps to find LIS length:
- You will search for an increasing subsequence for every element and then pick the one with the maximum length.
- You will start with fixing the ending point first and then go from there.
- You will decrease the indices and look for the second last element, and so on.
- Finally, you will select the subsequence with the highest length and declare it as LIS.
And this is how you find the Longest increasing subsequence using recursion. Now, implement this solution through a simple C++ code.
Implement the Recursion-Based Solution to Find the Longest Increasing Subsequence
You will be provided with a set with elements {10, 15, 13, 9, 21, 22, 35, 29, 64}. Now, you are to find the longest increasing subsequence in this set, which will come out to be the LIS{10, 13, 21, 22, 29, 64} and of length equal to six.
Code:
/* A C++ program to implement recursive solution
of LIS problem */
#include <bits/stdc++.h>
using namespace std;
/* To make use of recursive calls, this
the function will return two things:
1) We use curmaxending to get Length of LIS ending with element arr[n-1]
2) Overall maximum as the LIS may end with
an element before arr[N-1]. maxref is
used this purpose.
The value of LIS of a full array of size n
is stored in *max_ref, which is our final result
*/
int _lis(int arr[], int N, int* maxref)
{
/* Base case */
if (N == 1)
return 1;
// 'curmaxending' is length of LIS
// ending with arr[N-1]
int res, curmaxending = 1;
/* Recursively get all LIS ending with arr[0],
arr[1] ... arr[n-2]. If arr[i-1] is smaller
than arr[N-1], and max ending with arr[N-1]
needs to be updated, then update it */
for (int i = 1; i < N; i++) {
res = _lis(arr, i, maxref);
if (arr[i - 1] < arr[N - 1]
&& res + 1 > curmaxending)
curmaxending = res + 1;
}
// Compare curmaxending with the overall
// max. And update the overall max if needed
if (*maxref < curmaxending)
*maxref = curmaxending;
// Return length of LIS ending with arr[N-1]
return curmaxending;
}
// The wrapper function for _lis()
int lis(int arr[], int N)
{
// The max variable holds the result
int max = 1;
// The function _lis() stores its result in max
_lis(arr, N, &max);
// returns max
return max;
}
int main()
{
int arr[] = { 10, 15, 13, 9, 21, 22, 35, 29, 64 };
int N = sizeof(arr) / sizeof(arr[0]);
cout <<"Length of lis is "<< lis(arr, N);
return 0;
}
You have now discussed the recursive approach to find the Longest increasing subsequence with a code. This method has a time complexity of O(2n). If you look at the recursion tree of the above method, you will find some overlapping subproblems. That means you can still improve your time complexity. Now, see the dynamic programming-based solution to this problem.
Dynamic Programming Based Solution to Find the Longest Increasing Subsequence
Since the recursive approach uses a top-down approach, you will follow the bottom-up approach.
- First, make a 1D array of size n.
- Next, you must iterate it for each element from index 1 to n-1.
- You will iterate the elements with indices smaller than the current element in a nested loop for each element.
- In this nested loop, if you find the element’s value is lesser than the current element, then you will assign lis[i] with (lis[j]+1) and if (lis[j]+1) is greater than lis[i].
- Finally, you will traverse the entire lis[] array to find the maximum element, which will conclude your answer.
And this is how you solve this problem using dynamic programming. Now implement this solution through a simple C++ code.
Implement the Dynamic Programming Based Solution to Find the Longest Increasing Subsequence
You will be provided with a set with elements {10, 15, 13, 9, 21, 22, 35, 29, 64}. You are to find the longest increasing subsequence in this set, which will come out to be the LIS{10, 15, 21, 22, 35, 64} and of length equal to six.
Code:
//A C++ program to implement LIS problem using Dynamic Programming
#include <bits/stdc++.h>
using namespace std;
/* lis() returns the length of the longest
increasing subsequence in arr[] of size N */
int lis(int arr[], int N)
{
int lis[N];
lis[0] = 1;
/* Compute optimized LIS values in
bottom up manner */
for (int i = 1; i < N; i++) {
lis[i] = 1;
for (int j = 0; j < i; j++)
if (arr[i] > arr[j] && lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
}
// Return maximum value in lis[]
return *max_element(lis, lis + N);
}
/* Driver program to test above function */
int main()
{
int arr[] = { 10, 15, 13, 9, 21, 22, 35, 29, 64 };
int N = sizeof(arr) / sizeof(arr[0]);
printf("Length of longest increasing sub-sequence is %d\n", lis(arr, N));
return 0;
}
With this, you have come to an end of this tutorial. You will now look at what could be your next steps to conquer dynamic programming problems.
Advance your career as a MEAN stack developer with the Full Stack Web Developer - MEAN Stack Master's Program. Enroll now!
Next Steps
Your next stop in mastering dynamic programming problems should be Knapsack Problem. The knapsack problem is used to explain both the problem and the solution. It derives its name from the limited number of things that may be carried in a fixed-size knapsack. You are given a selection of varying weights and values; your objective is to cram as much worth into the knapsack as possible while staying within the weight limit.
If you're searching for a more in-depth understanding of software development that can help you carve out a successful career in the field, look no further. If that's the case, consider Simplilearn's Postgraduate Program in Full Stack Web Development, which is offered in collaboration with Caltech CTME, the world's largest technology education institution. This Post-Graduate Program will teach you how to grasp both front-end and back-end Java technologies, beginning with the basics and moving to more sophisticated Full Stack Web Development subjects. In this web development course, you'll study Angular, Spring Boot, Hibernate, JSPs, and MVC, which will help you get started as a full-stack developer.
If you have any questions or require clarification on this "Longest Increasing Subsequence" tutorial, please leave them in the comments section below. Our expert team will review them and respond as soon as possible.
