This article will consist of three parts:
- First, we will discuss the tabulation dp approach in continuation of the previous article.(/** link to dp 41 *****/.
- Next, we will discuss a new algorithm called the “Tabulation algorithm” to solve the problem of finding the longest increasing subsequence.
- In the last section, we will discuss the approach to printing the longest increasing subsequence.
Part 1: Writing the tabulation approach for finding LIS.
Prerequisite: /** link to dp-41 **/
Problem Link: Longest Increasing Subsequence
To convert the memoization approach to a tabulation one, create a dp array with the same size as done in memoization i.e dp[N][N+1].
- Now the base case is if(ind==n), we return 0. We can initialize the entire dp array as 0. In this way, we need to write the base case explicitly.
- The changing parameters in the recursive code are ind and prev_index. We will write them in the opposite direction of memoization.
- We will set for a loop of ind to range from n-1 to 0.
- If we look closely at the recursive tree, we will see a pattern that the second parameter, prev_index is always smaller than the first parameter ind. Therefore we will write the for loop for prev_index to start from ind-1 till -1.
- Next, we write the recursive logic inside the nested loops.
- We need to keep in that mind that we are storing prev_index in the dp array by making a coordinate shift (discussed in /** link to dp – 41 ** /).
- At last, we will print dp[0][0] as our answer.
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
int longestIncreasingSubsequence(int arr[], int n){
vector<vector<int>> dp(n+1,vector<int>(n+1,0));
for(int ind = n-1; ind>=0; ind --){
for (int prev_index = ind-1; prev_index >=-1; prev_index --){
int notTake = 0 + dp[ind+1][prev_index +1];
int take = 0;
if(prev_index == -1 || arr[ind] > arr[prev_index]){
take = 1 + dp[ind+1][ind+1];
}
dp[ind][prev_index+1] = max(notTake,take);
}
}
return dp[0][0];
}
int main() {
int arr[] = {10,9,2,5,3,7,101,18};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"The length of the longest increasing subsequence is "
<<longestIncreasingSubsequence(arr,n);
return 0;
}
Output:
The length of the longest increasing subsequence is 4
Time Complexity: O(N*N)
Reason: There are two nested loops
Space Complexity: O(N*N)
Reason: We are using an external array of size ‘(N+1)*(N+1)’. Stack Space is eliminated.
Java Code
import java.util.*;
class TUF{
static int longestIncreasingSubsequence(int arr[], int n){
int dp[][]=new int[n+1][n+1];
for(int ind = n-1; ind>=0; ind --){
for (int prev_index = ind-1; prev_index >=-1; prev_index --){
int notTake = 0 + dp[ind+1][prev_index +1];
int take = 0;
if(prev_index == -1 || arr[ind] > arr[prev_index]){
take = 1 + dp[ind+1][ind+1];
}
dp[ind][prev_index+1] = Math.max(notTake,take);
}
}
return dp[0][0];
}
public static void main(String args[]) {
int arr[] = {10,9,2,5,3,7,101,18};
int n = arr.length;
System.out.println("The length of the longest increasing subsequence is
"+longestIncreasingSubsequence(arr,n));
}
}
Output:
The length of the longest increasing subsequence is 4
Time Complexity: O(N*N)
Reason: There are two nested loops
Space Complexity: O(N*N)
Reason: We are using an external array of size ‘(N+1)*(N+1)’. Stack Space is eliminated.
Part 3: Space Optimization
If we closely we are using two rows: dp[ind+1][ ], dp[ind][ ],
So we are not required to contain an entire array, we can simply have two rows next and cur where next corresponds to dp[ind+1] and cur to dp[ind].
After declaring next and cur, replace dp[ind+1] to next and dp[ind] with cur and after the inner loop executes, we will set next = cur, so that the cur row can serve as next for the coming iteration.
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
int longestIncreasingSubsequence(int arr[], int n){
vector<int> next(n+1,0);
vector<int> cur(n+1,0);
for(int ind = n-1; ind>=0; ind --){
for (int prev_index = ind-1; prev_index >=-1; prev_index --){
int notTake = 0 + next[prev_index +1];
int take = 0;
if(prev_index == -1 || arr[ind] > arr[prev_index]){
take = 1 + next[ind+1];
}
cur[prev_index+1] = max(notTake,take);
}
next = cur;
}
return cur[0];
}
int main() {
int arr[] = {10,9,2,5,3,7,101,18};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"The length of the longest increasing subsequence is "
<<longestIncreasingSubsequence(arr,n);
return 0;
}
Output:
The length of the longest increasing subsequence is 4
Time Complexity: O(N*N)
Reason: There are two nested loops.
Space Complexity: O(N)
Reason: We are only using two rows of size n.
Java Code
import java.util.*;
class TUF{
static int longestIncreasingSubsequence(int arr[], int n){
int next[]=new int[n+1];
int cur[]=new int[n+1];
for(int ind = n-1; ind>=0; ind --){
for (int prev_index = ind-1; prev_index >=-1; prev_index --){
int notTake = 0 + next[prev_index +1];
int take = 0;
if(prev_index == -1 || arr[ind] > arr[prev_index]){
take = 1 + next[ind+1];
}
cur[prev_index+1] = Math.max(notTake,take);
}
next = cur.clone();
}
return cur[0];
}
public static void main(String args[]) {
int arr[] = {10,9,2,5,3,7,101,18};
int n = arr.length;
System.out.println("The length of the longest increasing subsequence is
"+longestIncreasingSubsequence(arr,n));
}
}
Output:
The length of the longest increasing subsequence is 4
Time Complexity: O(N*N)
Reason: There are two nested loops.
Space Complexity: O(N)
Reason: We are only using two rows of size n.
Part 2: Tabulation algorithm to find the length of the longest increasing subsequence.
Algorithm description:
We need to find the length of the longest increasing subsequence if an array of length n.
For example:
Now in this algorithm, we need to build logic to get an array( say dp), For this particular example, the dp array will look like this:
Now every cell value in this dp array is defined as follows:
For every index i of the array ‘arr’;
dp[ i ] is the length of the longest increasing subsequence that is possible that end with index ind of the original array.
Few examples:
(i) For i = 0, dp[i] =1 , therefore LIS length with the element arr[0], i.e 5 as its last element is 1. The case :[ 5 ].
(ii) For i = 4, dp[i] =3 , therefore LIS length with the element arr[4], i.e 16 as its last element is 3. The case :[ 5, 11, 16 ].
Once we get this dp array our job is to simply return the maximum cell value of the entire array as the length of the longest increasing subsequence.
Now, the main question arises: how do we get this dp[ ] array? The following section explains the logic and the approach.
Logic and approach for the dp array
We know that a single element can always be considered to be included in the LIS, as it can not break any rule of forming the LIS. Therefore we can initialize the dp array by 1, it simply means that currently, LIS is having only that particular men=mber element itself ([5], [4], [11], …).
Now let us manually try to find dp[i], for some indexes in order to understand the algorithm.
(i) For i = 0, 5 can be the only element that can be in the LIS, as there is no element before it therefore the final dp[i] for i=0, will be 1 only (marked in red).
(ii) For i = 1, 4 can be the only element that can be in the LIS, as there is only element 5 before but 5 is greater than 4 so cannot be considered in the LIS. therefore the final dp[i] for i=1, will be 1 only (marked in red).
(iii) For i = 2, either 5 or 4 can be considered in the LIS as the last element of 11. We will run a loop that checks all prev_index and if the arr[prev_index] < arr[i], we can simply say that the element should be updated to 1+dp[prev_index]. 1 means that we are adding one element to the LIS, here 11, and also the LIS of the previous indexes which are given by dp[prev_index]. Note we will update only for that prev_index, whose prev_index is the maximum. We will discuss this in the next to next case also.
(iv) For i=3, it is the similar case as (ii), so dp[3] = 1.
(v) For i=4, we will again loop for all the prev_index of 4 and we make the following observations:
- LIS ending at element 5 can be considered (dp[0] = 1)
- LIS ending at element 4 can also be considered. (dp[1] = 1)
- LIS ending at element 11 can also be considered. (dp[1] = 2)
Out of all these possible choices, we will consider LIS ending at element 11 because if we consider it we will have 2 elements of that [ 5, 11] and element 16 itself, giving us a LIS of length 3, the maximum. All other options were giving a LIS of length 2.
This is the reason that we consider that prev_index whose dp[prev_index] is maximum.
Algorithm approach:
The algorithm approach can be stated as follows:
- Run an outer loop running from 0 to n-1. Every outer loop iteration will find the dp[i] value.
- Nest another loop inside it. For particular index i, this inner loop will help us to find the maximum value of dp[prev_index].
- Now inside the inner loop, we will first of all see that the element at the prev_index is smaller than the element at index i. If it is, we update dp[i] with the max(1+dp[prev_ind],dp[prev_index]).
- At last, we will loop over the dp array and return its largest value as our answer.
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
int longestIncreasingSubsequence(int arr[], int n){
vector<int> dp(n,1);
for(int i=0; i<=n-1; i++){
for(int prev_index = 0; prev_index <=i-1; prev_index ++){
if(arr[prev_index]<arr[i]){
dp[i] = max(dp[i], 1 + dp[prev_index]);
}
}
}
int ans = -1;
for(int i=0; i<=n-1; i++){
ans = max(ans, dp[i]);
}
return ans;
}
int main() {
int arr[] = {10,9,2,5,3,7,101,18};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"The length of the longest increasing subsequence is "
<<longestIncreasingSubsequence(arr,n);
return 0;
}
Output:
The length of the longest increasing subsequence is 4
Time Complexity: O(N*N)
Reason: There are two nested loops.
Space Complexity: O(N)
Reason: We are only using two rows of size ‘N’.
Java Code
import java.util.*;
class TUF{
static int longestIncreasingSubsequence(int arr[], int n){
int dp[]=new int[n];
Arrays.fill(dp,1);
for(int i=0; i<=n-1; i++){
for(int prev_index = 0; prev_index <=i-1; prev_index ++){
if(arr[prev_index]<arr[i]){
dp[i] = Math.max(dp[i], 1 + dp[prev_index]);
}
}
}
int ans = -1;
for(int i=0; i<=n-1; i++){
ans = Math.max(ans, dp[i]);
}
return ans;
}
public static void main(String args[]) {
int arr[] = {10,9,2,5,3,7,101,18};
int n = arr.length;
System.out.println("The length of the longest increasing subsequence is
"+longestIncreasingSubsequence(arr,n));
}
}
Output:
The length of the longest increasing subsequence is 4
Time Complexity: O(N*N)
Reason: There are two nested loops.
Space Complexity: O(N)
Reason: We are only using two rows of size ‘N’.
Part 3: Printing the LIS
In order to print the LIS, we maintain a separate array along with a dp array (say hash).
Whenever we update our dp[i] value in the inner loop, we know that for index i, the previous index is prev_index. Therefore we simply store prev_index to hash[ i ]. In this way, we will have a way to trace back the LIS.
Whenever we have computed the entire dp array and we find the maximum value in it. We store that maximum value’s index in a variable ( say last_index). Now with this last_index, and the hash array we can trace back the LIS elements.
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
int longestIncreasingSubsequence(int arr[], int n){
vector<int> dp(n,1);
vector<int> hash(n,1);
for(int i=0; i<=n-1; i++){
hash[i] = i; // initializing with current index
for(int prev_index = 0; prev_index <=i-1; prev_index ++){
if(arr[prev_index]<arr[i] && 1 + dp[prev_index] > dp[i]){
dp[i] = 1 + dp[prev_index];
hash[i] = prev_index;
}
}
}
int ans = -1;
int lastIndex =-1;
for(int i=0; i<=n-1; i++){
if(dp[i]> ans){
ans = dp[i];
lastIndex = i;
}
}
vector<int> temp;
temp.push_back(arr[lastIndex]);
while(hash[lastIndex] != lastIndex){ // till not reach the initialization value
lastIndex = hash[lastIndex];
temp.push_back(arr[lastIndex]);
}
// reverse the array
reverse(temp.begin(),temp.end());
cout<<"The subsequence elements are ";
for(int i=0; i<temp.size(); i++){
cout<<temp[i]<<" ";
}
cout<<endl;
return ans;
}
int main() {
int arr[] = {10,9,2,5,3,7,101,18};
int n = sizeof(arr)/sizeof(arr[0]);
longestIncreasingSubsequence(arr,n);
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int longestIncreasingSubsequence(int arr[], int n){
vector<int> dp(n,1);
vector<int> hash(n,1);
for(int i=0; i<=n-1; i++){
hash[i] = i; // initializing with current index
for(int prev_index = 0; prev_index <=i-1; prev_index ++){
if(arr[prev_index]<arr[i] && 1 + dp[prev_index] > dp[i]){
dp[i] = 1 + dp[prev_index];
hash[i] = prev_index;
}
}
}
int ans = -1;
int lastIndex =-1;
for(int i=0; i<=n-1; i++){
if(dp[i]> ans){
ans = dp[i];
lastIndex = i;
}
}
vector<int> temp;
temp.push_back(arr[lastIndex]);
while(hash[lastIndex] != lastIndex){ // till not reach the initialization value
lastIndex = hash[lastIndex];
temp.push_back(arr[lastIndex]);
}
// reverse the array
reverse(temp.begin(),temp.end());
cout<<"The subsequence elements are ";
for(int i=0; i<temp.size(); i++){
cout<<temp[i]<<" ";
}
cout<<endl;
return ans;
}
int main() {
int arr[] = {10,9,2,5,3,7,101,18};
int n = sizeof(arr)/sizeof(arr[0]);
longestIncreasingSubsequence(arr,n);
return 0;
}
Output:
The subsequence elements are 2 5 7 101
Time Complexity: O(N*N)
Reason: There are two nested loops.
Space Complexity: O(N)
Reason: We are only using two rows of size ‘N’.
Java Code
import java.util.*;
class TUF{
static int longestIncreasingSubsequence(int arr[], int n){
int[] dp=new int[n];
Arrays.fill(dp,1);
int[] hash=new int[n];
Arrays.fill(hash,1);
for(int i=0; i<=n-1; i++){
hash[i] = i; // initializing with current index
for(int prev_index = 0; prev_index <=i-1; prev_index ++){
if(arr[prev_index]<arr[i] && 1 + dp[prev_index] > dp[i]){
dp[i] = 1 + dp[prev_index];
hash[i] = prev_index;
}
}
}
int ans = -1;
int lastIndex =-1;
for(int i=0; i<=n-1; i++){
if(dp[i]> ans){
ans = dp[i];
lastIndex = i;
}
}
ArrayList<Integer> temp=new ArrayList<>();
temp.add(arr[lastIndex]);
while(hash[lastIndex] != lastIndex){ // till not reach the initialization value
lastIndex = hash[lastIndex];
temp.add(arr[lastIndex]);
}
// reverse the array
System.out.print("The subsequence elements are ");
for(int i=temp.size()-1; i>=0; i--){
System.out.print(temp.get(i)+" ");
}
System.out.println();
return ans;
}
public static void main(String args[]) {
int arr[] = {10,9,2,5,3,7,101,18};
int n = arr.length;
longestIncreasingSubsequence(arr,n);
}
}Output:
The subsequence elements are 2 5 7 101
Time Complexity: O(N*N)
Reason: There are two nested loops.
Space Complexity: O(N)
Reason: We are only using two rows of size ‘N’.
Special thanks to Anshuman Sharma for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article. If you want to suggest any improvement/correction in this article please mail us at [email protected]