DP 42. Printing Longest Increasing Subsequence | Tabulation | Algorithm

Please watch the video at 1.25x for a better experience.

a

In this video, we solve the LIS DP using tabulation method, then we go on to print the LIS as well.

[krishnans]

Another approach which I found to be intuitive: We can store the elements of the array without duplicates in increasing order (Can be easily done with the help of TreeSet in java or set in cpp). Then again store these elements in a new array and find the LCS of the original array and the newly computed array. The LCS of these 2 arrays will be the LIS. For printing the LIS, we can use the same approach used for printing LCS.

[muditkhanna]

the thing you did with the comparing dp[prev]+1<dp[i] made me remind the dijkstra edge relaxation

[oblivion_]

Understood. Words cannot express how thankful we are to you for this series.

[anmolverma]

To printing there is a simpler approach and here is the code with explanation for it =>
int mx = res;
vector<int>lis;
for(int i = n-1;i>=0;--i){
if(dp[i] == mx){
lis.emplace_back(v[i]);
mx--;
}
}
reverse(begin(lis), end(lis));
for(auto &it : lis) cout<<it<<" ";
cout<<"\n";
Explanation -> the resumt will be storing the longest increasing subsequence(LIS), store it in a mx variable, and declare a list lis, Iterate over dp from n-1 to 0. If dp[I[ == nx then it's the LIS and store the v[I] in lis vector and decrease mx. Now m-1 will be the prev element which was the part of LIS and store it in lis vector and decrease mx. Do this and finally reverse the list and here you have it!!!.

Full code=>

int lengthOfLIS(vector<int>& v) {
const int n = v.size();
vector<int>dp(n, 1);
int res = -1;
for(int i = 0;i<n;++i){
for(int prev = 0;prev<i;prev++){
if(v[i]>v[prev]){
dp[i] = max(dp[i], 1 + dp[prev]);
}
}
res = max(res, dp[i]);
}
int mx = res;
vector<int>lis;
for(int i = n-1;i>=0;--i){
if(dp[i] == mx){
lis.emplace_back(v[i]);
mx--;
}
}
reverse(begin(lis), end(lis));
for(auto &it : lis) cout<<it<<" ";
cout<<"\n";
return res;
}

[chandrachurmukherjeejucse]

Understood. Solved this with second approach just 2 days before. Great content!

[keshavbiyani]

I am so happy that you shared the recursive then memoized then came to this tabulation code. I never understood the videos that directly explained this 1D dp solution you explained in the end

[sumitkevlani]

This approach comes to work when we have said to print only one LIS for the array but if we want to all the LIS of the array then we need to use BFS kind of algorithm.

[karanprabhakar]

Hi @take U forward this method can also be implemented with queue
And one more thing, if the question changes to print all such subsets ( as in this case, you are printing only one ), queue implementation will be handy

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <limits.h>
#include <string>
using namespace std;

int main() {
int n = 10 ;
vector<int> arr = {10, 22, 9, 33, 21, 50, 41, 60, 80, 1};

vector<int> dp(n, 0);
dp[0] = 1;
int omax = 0;
int index = -1;

for(int i = 1 ; i < n ; i++) {
int max = 0;
for(int j = 0 ; j < i ; j++) {
if(arr[i] > arr[j]) {
if(max < dp[j]) {
max = dp[j];
}
}
}
dp[i] = max+1;
if(omax < dp[i]) {
omax = dp[i];
index = i;
}
}

if(omax == 0) {
omax += 1;
index = 0;
}

cout<<omax<<endl;
queue<pair<int, string>> myqueue;
myqueue.push(make_pair(index, to_string(arr[index])));

while(!myqueue.empty()) {
pair<int, string> temp = myqueue.front();
int i = temp.first;
string val = temp.second;
int value = dp[i] - 1;
myqueue.pop();

if(i == 0) {
cout<<val<<endl;
continue;
}

for(int pq = 0 ; pq < i ; pq++) {
if(dp[pq] == value) {
myqueue.push(make_pair(pq, to_string(arr[pq]) + " " +val));
}
}

}


return 0;
}


Output

6
10 22 33 50 60 80
10 22 33 41 60 80

[tori_bam]

I cannot thank you enough for this lesson. Really appreciate for this step by step build ups

[raghavmanish]

understood time it takes time but finally smjh aa hi gya...thanku striver

[siddheshpawar]

I think we don't have to use hash for printing sequence. We can start from an index in our array where we got maxi value and go in reverse manner. For every index we will check if our value in dp less by 1 as that of maxi then it will part of sequence we will reduce maxi by one for further finding the elements.

[ritikshandilya]

really really awesome approach, thanks for great learning Striver

[studyonline]

6:03 The intuition behind this tabulation is Fibonacci (frog jump problem - similar to DP-04 of this playlist) but the condition could be like -


Frog must jump in increasing fashion using maxing stones possible. In this regard,
Plz spend 2 mins on this to get the intuition.


(Input array can be used to simulate the frog-stone representation. EX - array = [2, 5, 1, 7], the first stone is at a distance of 2 from the start, then the second stone is 5 units away from the previous stone etc)

Frog(*), = stones separated by a variable distance (based on the input array)

__*__ **____** **____** __*__ ____ ____ __*__ (WITH 7 stones)

"Frog can start from any of the stones"

In the above example : frog jumped say a distance k from stone 1 to stone 4, then it cannot jump to another stone say 5 or 6 and it has only one stone left, which is >k distance -> stone 7 : So the number of stones it used are 3. Longest Increasing Sequence = 3.


CASE - 2:
stones distances = Input Array = [1, 2, 5, 7, 15, 3], Ascending order
Stone and frog representation:

__1__ __2__ __5__ __7__ __15__ __3__

Now the frog can use 1, 2, 5, 7, 15 - LISubseq = 5

CASE - 3:
stones distances = Input Array = [6, 5, 4, 3, 2, 1], Descending order
Stone and frog representation:


(Stone 1 is already at a distance 6 from the start) __6__ __5__ __4__ __3__ __2__ __1__

Intuitively, * cannot go to next stone from any of the starting stone, the LIS = 1 (num of stones used).


A recap of the concept of DP-4 (a variation - frog jump in increasing fashion - inspired by Fibonacci),
TC=O(n^2), SC=O(n) for dp and O(n) for recursion stack.

#Recursion LOGIC

The main intent of this comment is to let you guys know that you can use the Fibonacci logic(that you already know). You can think it of a fibonacci problem - Assume a frog can jump from any of the valid index(0<=ind<n and a[ind]<a[n]) to the last index 'n'. Repeat the process of reaching every index from the start index and start filling the dp table with the number of steps to reach the index for which the function was called and pick out the max from the dp array.
(Although this code runs slower, not effecient, this is accepted on leetcode)


# inspired by Fibonacci (frog jump) in PYTHON
n=len(a)
dp=[-1]*n

def f(n):
if n==0:
dp[n]=1
return 1
if dp[n]!=-1: return dp[n]
maxi=-1e9
for k in range(n-1, -1, -1): #K previous steps
if a[k]<a[n]:
maxi=max(maxi, 1+f(k))
dp[n]=maxi if maxi!=-1e9 else 1
return dp[n]

#Last index may or may not include in the answer (and so is the case with all indices), so max of all the calculated answers gives us the final result.

i=n-1
while i>=0:
f(i) #fills up the dp table for index i and all the indices where the value is < a[i]
i-=1
ans=max(dp)
return ans if ans!=-1e9 else 1


#T #A #B #U #L #A #T #I #O #N

If you can write the tabulation logic for the above recursive function, you'd start from index 0 and not the last index (in bottom-up fashion); you'd calculate the values for all the positions in the array and store the results in the dp array(which is what is being done here).

My tabulation logic based on the above function is in the REPLIES for this comment (but don't look at it until you wrote it by yourself), as you can easily
THINK
and write the code and end up seeing it is the same as what Striver wrote in this lecture. [Try to solve it while keeping this in mind plz :) ]

Thanks, Striver bhai, for making me think this way.

[anuragC]

This is the only one that I have not understood properly till now. Till the memoization section it was fine but the tabulation, I did not exactly understand the inner loop

[jonu.]

It can be solved in O(NlogN) using Patience Sorting algorithm

[keyurraval]

Got the same question in my Capgemini test today. Thanks Bhaiya

[Harshit]

Understood, respect! The last method could actually be used for Longest Ideal Subsequence also which has been giving TLE eternally :P
Thanks a ton!

[arkasarkar]

6:17 optimised tabulation, 17:40 -> print lis, 23:13 final code

[TheDev]

Similar prob. : 1626. Best Team With No Conflicts

[atifmirza]

00:01 Tabulation approach is discussed as an alternative to memoization for solving the longest increasing subsequence problem

02:17 Copy the recurrence and follow coordinate shift

06:29 The longest increasing subsequence can have different lengths depending on the last element.

08:48 The algorithm computes the longest increasing subsequence (LIS) for a given sequence.

13:10 Printing longest increasing subsequence using tabulation.

15:28 Implementing the tabulation method to find the Longest Increasing Subsequence in an array

19:46 Finding the longest increasing subsequence using tabulation.

21:40 The longest increasing subsequence can be obtained by following the index values in reverse order

25:38 Printing longest increasing subsequence using tabulation algorithm.

Crafted by Merlin AI.