DP 42. Printing Longest Increasing Subsequence | Tabulation | Algorithm
ฝัง
- เผยแพร่เมื่อ 27 ก.ย. 2024
- Lecture Notes/C++/Java Codes: takeuforward.o...
Problem Link: bit.ly/3rVoIoq
Please watch the video at 1.25x for a better experience.
Pre-req for this Series: • Re 1. Introduction to ...
a
Make sure to join our telegram group for discussions: linktr.ee/take...
Full Playlist: • Striver's Dynamic Prog...
In this video, we solve the LIS DP using tabulation method, then we go on to print the LIS as well.
If you have not yet checked our SDE sheet, you should definitely do it: takeuforward.o...
You can also get in touch with me at my social handles: linktr.ee/take...
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.
nice approach
//Nice Approach -- JAVA Code
import java.util.*;
public class Main
{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int arr1[] = new int[n];
TreeSet ts =new TreeSet();
for(int i=0;idp[ind1-1][ind2]){
ind2--;
}else{
ind1--;
}
}
}
//Reverse the LCS arrayList
Collections.reverse(ans);
System.out.println(ans);
}
}
really intuitive,thanks
better approach would be to just utilize the dp array for it , as we know the difference between the last element in our sequence and second last element is just 1 , so what we can do , we will start iterating over array from last --> 0, when ever we find dp[i] == max , we will add , or print , and then decrease our max to max--; so that no we try to find second last element and so on.
for(int index = n - 1; index >= 0 ; index--){
if ( dp[index] == max){
System.out.print( arr[index] +" ");
max--;
}
}
But that will again be n2 solution. So doesn't help.
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
Plz read the comment first.
#code in python
def f():
dp=[1]*n
for i in range(n):
for k in range(i):
if a[k]
thanks brother
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
#include
#include
#include
#include
#include
using namespace std;
int main() {
int n = 10 ;
vector arr = {10,22,9,33,21,50,41,60,80,1};
vector 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
Somethings are not right in this code.. instead of index==0...it should be dp[index]==1 to print lis...and d[pq]==value && nums[i]
@@harpic949 hi Aditya if you run it in c++ , it will work. I == 0 means you have reached start of it and hence you can safely exit
can you convert it into Tabulation aapne poori series mei aisi hi recursion likhwayi hai PLease REPLY ! 5 ghante se baitha hu shi answer nhi aa rha
#include
int fun(int i,int prev,int arr[],int n, vector &dp)
{
if(iarr[i])
len=max(len,1+fun(i-1,i,arr,n,dp));
return dp[i][prev]=len;
}
int longestIncreasingSubsequence(int arr[], int n)
{
// Write Your Code here
vector dp(n,vector(n+1,-1));
return fun(n-1,n,arr,n,dp);
}
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.
#include
int fun(int i,int prev,int arr[],int n, vector &dp)
{
if(iarr[i])
len=max(len,1+fun(i-1,i,arr,n,dp));
return dp[i][prev]=len;
}
int longestIncreasingSubsequence(int arr[], int n)
{
// Write Your Code here
vector dp(n,vector(n+1,-1));
return fun(n-1,n,arr,n,dp);
}
@@ajaysaini5314bhai eska tabulation hai ??
Dp on trees and graphs plz
he did already
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.
that's what i thought too
Yes, you can do that too, takes another N to backtrack if the length is smaller of lis.
@@takeUforward
# o(nlogn) solution
int longestIncreasingSubsequence(int a[], int n)
{
vector dp;
dp.push_back(a[0]);
for(int i=1;idp.back()) dp.push_back(a[i]);
else
{
int idx=lower_bound(dp.begin(),dp.end(),a[i])-dp.begin();
dp[idx]=a[i];
}
}
return dp.size();
}
same
@@Rk-tm8z best
Understood. Solved this with second approach just 2 days before. Great content!
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
me too bro
inner loop is for prev as prev can be any index from (currInd - 1 ) to -1 (if their is no prev)
@@deepaktiwari7059 pata h yaar itna to..par ye utna intutive nahi h
@@harpic949 Bro tabulation intutive hota bhi nhi hai we just do it for auxillary space optimization, only recursive solution are inituitive
++
It can be solved in O(NlogN) using Patience Sorting algorithm
How to learn these many algorithms and improve our thinking it really very scary bro
6:17 optimised tabulation , 17:40 -> print lis ,23:13 final code
Earlier ( in previous video) it was not allowed ( was not getting ac ) to have n^2 dp but now in tabulation it got accepted how ?
UNDERSTOOD......Thank You So Much for this wonderful video............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
I cannot thank you enough for this lesson. Really appreciate for this step by step build ups
understood .....this time it takes time but finally smjh aa hi gya...thanku striver
Similar prob. : 1626. Best Team With No Conflicts
Understood, respect! The last method could actually be used for Longest Ideal Subsequence also which has been giving TLE eternally :P
Thanks a ton!
the thing you did with the comparing dp[prev]+1
Got the same question in my Capgemini test today. Thanks Bhaiya
for which position?
Doggy style position ke liye😂😂
thanks for sharing your experience👌
A bit simpler and easier to understand code (without using the extra hash array) using the Tabulation method taught by striver:
vector printingLongestIncreasingSubsequence(vector arr, int n) {
//Step 1: Calculating length of one of the LIS
vector dp(n,1);
for(int ind=1;ind
better approach would be to just utilize the dp array for it , as we know the difference between the last element in our sequence and second last element is just 1 , so what we can do , we will start iterating over array from last --> 0, when ever we find dp[i] == max , we will add , or print , and then decrease our max to max--; so that no we try to find second last element and so on.
for(int index = n - 1; index >= 0 ; index--){
if ( dp[index] == max){
System.out.print( arr[index] +" ");
max--;
}
}
how can you be sure than wo isika part hai, there is also a possibility that us index tak ka uska LIS 2 hai but wo current index ka part hi nahi hai
@@pratikshadhole6694 The elements in the subsequence does not matter, only the order must be maintained.
really really awesome approach , thanks for great learning Striver
Trying all given possibilites on comments, I think the code striver is teaching is best though its not intutive
Understood Sir. Thank you so much.
Its not the most optimal and ideal way to print, there is no need of hash table, you can iterate max_idx in this way. 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.. Have a look at my code.
int lengthOfLIS(vector& nums) {
int n = nums.size();
vector dp(n, 1);
int maxi = 1;
int max_idx = -1;
for(int i = 0; i < n; i++){
for(int prev = 0; prev< i; prev++){
if(nums[prev] < nums[i]){
dp[i] = max(dp[i], 1 + dp[prev]);
}
}
if(dp[i] > maxi){
maxi = dp[i];
max_idx = i;
}
}
while(max_idx >= 0){
cout nums[idx] && dp[max_idx] == dp[idx] + 1) break;
--idx;
}
max_idx = idx;
}
return maxi;
}
};
Striver please pin this comment if you find it appropriate
This is the Best DP series but, got to say that this question was the least intuitive one to solve.
for next/curr to save space for this problem we only need one array since by the time we update the index it's already used
that space optimization trick using next and prev is dope!
bro I didnt get that can u tell which video is he refereing to
@@danishsharma496 watch the first video of dp on strings
Hey striver. What is the timeline for the updation of notes. It's not there in the DP notes section.
can we directly use this tabulation approach in interviews for prev lis question
I think we can do it in NlogN + PlogP where P is LIS size
please provide documentation or write ups of the this algorithms please
bhaiya confuse about co-ordinate change please clear doubt
why is it that if we apply increasing for loop that is 0 to n for index and -1 to index-1 for previous index rather than the decreasing way mentioned in the video the answer is coming wrong, it would be really helpful if anyone could explain💡
I also have the same doubt, not able to understand how Striver changed it from recursion to tabulation
Hi Hardik, you cannot apply index from 0->n because while calculating dp[i] it is dependent on dp[i+1] so if you do it from 0->n intilally all will zero ahead of that index and you will get wrong answer. But while calculating it from n->0 the ahead one will be already calculated and add to the answer. Hope this helps
bro its bottom up nah so we do it in reverse way only, for that you shd make recursive equation from the n-1 idx and ques will be longest decreasing sequence for that to implement
why are second parameter going in +1 states?
the best thing about striver vaiyya is he normalize unsuccessful submission, i mean i used to think coder like them get successful submission at the first time itself and are never wrong , now i dont get panic when i see LTS or error or anything , it feels like okk lets try again :)
same
Didn't completely get that state shift approach. Could appreciate more problems involving that. Can you or someone pls suggest any related problems?
Please watch previous videos he explained we did shift so that it can work with dp as dp can't contain a negative index that is why we did +1 to make -1 prev_ind start from 0
@@ugthesep5706 oh ok. thanks!
printing O(N)
// printing lis
int temp = omax;
String lis = "";
for(int i = dp.length-1;i>=0 && omax!=0;i--){
if(dp[i] == omax){
lis = nums[i] +" "+lis;
omax-- }
}
understood the initial tabulation , Thanks
UNDERSTOOD!!!!🔥🔥🔥🔥
Last 4 mins ,.. Striver on God Mode
UNDERSTOOD
Why we cannot start from beginning like we used to do in other problems
Understood !!
Thanks Striver. Understood.
Understood!
Why did you all of a sudden reverse the iteration for memoization and tabulation
In Previous videos in memoization u went from n-1 -> 0, but here you reversed it
And this is very confusing,
Really definition of previous index is previous index, I think you could have explain that part in a better way !!1
Understood
we have used N*N sized array in tabulation also then why it is giving error in memoization only ?
second parameter was not always stored in +1 state in memoization as you stated in this video at 3.35. Why have you taken the index+1 as second parameter whereas in the memoization it was just index by updatiing about its current index which is actually greater than the previous index's value.
Because we are converting prevIndex whose range is between (n-1 to -1) to (n to 0) so, for every value that denotes prevIndex should be incremented by +1,that's why even when we are returning the answer instead of returning of [0][-1] we are return [0][-1+1].
not understood why index+1 at 3.40
Really challanging for me to make it today >>>
understood
Striver aka Raj brother one small correction @ 6:54
dp[i] = signifies the longest LIS that ends at i.
Correct is dp[i] = signifies LIS that starts at i
Bcoz ur Recursion call was f(0,-1) 0 to N. Thereby Tabulation code is N to 0.
So dp[i] is when LIS is starting from ith index till End (N-1).
I hope i am correct. Please someone let me know. Also like and support if it's correct.
But for the Next New Printing Code
Dp[i] = signifies the longest LIS that ends at i.
im not sure but his recurisive calls for tabulation approach are from n->0 hence tabulation from 0->n-1 , so dp[i] ends at i is correct imo
thankyou so so much sir
Thankyou @striver
I face problem while converting memo solution to tabulation solution how to overcome that?
thanks
Understood !! ❤
Understood!!Thank you
is printing LIS asked in interviews I am planning on leaving this
Thanks for that 👍
why are we adding +1 to prev if we're using range -1 to ind-1 in tabulation?
because prev's initial value is -1 which is not a valid array index.
Because we are converting prevIndex whose range is between (n-1 to -1) to (n to 0) so, for every value that denotes prevIndex should be incremented by +1,that's why even when we are returning the answer instead of returning of [0][-1] we are return [0][-1+1] @aditi1729 .
Bhaiya can u teach how to do dfs with memoization?
Dfs already uses stack
DFS has no overlaping Subsequence ,so no point of using Memoization there!!!!!!
🔥
can you provide the handwritten notes of dp series??
when i am checking (1+dp[j]>dp[i]) inside if then it is giving TLE but if i include this condition in if then it is passing all TCs. Can you explain plz?
Why do u want to create another array i.e. hash and make the things complicated ?
My Approach :
vectordp(n,1);
for(int i=0;i
it is perfect!!
But it fails @gfg where question ask to returns the Longest Increasing subsequence which is lexicographically smallest corresponding to the indices of the elements
Overall nice 🙂
understood
but what is there are more than one LISs.
at 4:46 i write the same code but runtime error someone help pls
paste your code here, will try to correct it
in arr it should be prev_ind+1
"Understood"!
we can't find notes for these videos , and I know java only. Please provide with the source code also.PLease
Understood
Understood,
I think we can also do without hash array
Where ever we find maxi we can store in ans
And in every loop keeping value in some curr array
Most Efficient Code:-
#include
int longestIncreasingSubsequence(int arr[], int n){
vector lis;
lis.push_back(arr[0]);
for(int i=1;i
When prev_ind == -1 then arr[ind] > arr[prev_ind] why this is not giving runtime error?
becoz of shortcircuit in logical or operator(if first statement is true then next statement will not execute)
Striver could you please upload the code and the notes for the videos from 38.
why a dp array of N+1 x N + 1 ??
you can make the dp array of dp[N][N];
but then your base case will gets changed
base case --> new
if(ind == nums.length-1){
if(prev == 0 || nums[ind]>nums[prev-1]) return 1;
return 0 ;}
Another approach
vector longestIncreasingSubsequence(int n, vector& arr) {
// Code here
vector dp (n+1, 1);
for(int idx = 0; idx
understood!!
understood✨
Understood !
understood sir🙏🙏
Us
Not understood, last mai kaafi tezii se kuch bhi krdia
Understood bhaiya !!!
ye code to khatam hi nhi ho rha 😅😅😂😂😂😂 ... Striver G.O.A.T
Understood ❤
22:00
Unsderstood
What if I do this after filling dp[]?
idx; // get it while filling dp, its idx at which we get max length
mx; // stores the max Length
vector v;
v.push_back(a[idx]);
for(int i=idx-1; i>=0; i--)
{
if(a[i]
understood😄😄
US
US
Understood !!1
Tough question bap re
this was a little too fast..u should have taken little more time to explain properly how lis is printed
mai padhte/revise karte karte thak gaya lekin yeh banda padhate hue nahi thaka!!
US :)
us