DP 42. Printing Longest Increasing Subsequence | Tabulation | Algorithm

  Рет қаралды 244,401

take U forward

take U forward

Күн бұрын

Пікірлер: 305
@krishnans1665
@krishnans1665 2 жыл бұрын
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.
@goooo9561
@goooo9561 2 жыл бұрын
nice approach
@pranavkorhale5089
@pranavkorhale5089 2 жыл бұрын
//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); } }
@rishabhgupta9846
@rishabhgupta9846 Жыл бұрын
really intuitive,thanks
@inderjotsingh5868
@inderjotsingh5868 Жыл бұрын
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--; } }
@abhishekkarn8918
@abhishekkarn8918 7 ай бұрын
But that will again be n2 solution. So doesn't help.
@muditkhanna8164
@muditkhanna8164 Жыл бұрын
the thing you did with the comparing dp[prev]+1
@oblivion_5910
@oblivion_5910 2 жыл бұрын
Understood. Words cannot express how thankful we are to you for this series.
@anmolverma2911
@anmolverma2911 Жыл бұрын
To printing there is a simpler approach and here is the code with explanation for it => int mx = res; vectorlis; 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
@ChillLavaRed
@ChillLavaRed 9 ай бұрын
consider for (int i = maxIndex; i >= 0 && maxLen > 0; --i) { if (dp[i] == maxLen && (ans.empty() || ans.back() > nums[i] ) { ans.push_back(nums[i]); maxLen--; } } to make sure its not a wrong ans
@mightygerman
@mightygerman 5 ай бұрын
But bro we have to return array with smaller indexwise lexographically. Note - A subsequence S1 is Index-wise lexicographically smaller than a subsequence S2 if in the first position where S1 and S2 differ, subsequence S1 has an element that appears earlier in the array arr than the corresponding element in S2.
@vattiyeshwanth282
@vattiyeshwanth282 5 ай бұрын
I think this is wrong brother see for the case [5,4,5]--> dp array will be [1,2,1]--> which makes it to take [5,4] as the longest increasing subsequence, and which is not the case.
@princiagrawal1428
@princiagrawal1428 5 ай бұрын
​@@vattiyeshwanth282I think that the DP array for case [5,4,5] will be [1, 1, 2]. First, I will insert 5 into my answer vector, then decrement `max`. `Max` will be 1, so I can push 4 into my answer vector. Finally, I will reverse the answer vector, resulting in [4, 5], which is correct.
@atifmirza9168
@atifmirza9168 Жыл бұрын
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.
@chandrachurmukherjeejucse5816
@chandrachurmukherjeejucse5816 Жыл бұрын
Understood. Solved this with second approach just 2 days before. Great content!
@karanprabhakar72
@karanprabhakar72 2 жыл бұрын
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
@harpic949
@harpic949 2 жыл бұрын
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]
@karanprabhakar72
@karanprabhakar72 2 жыл бұрын
@@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
@ajaysaini5314
@ajaysaini5314 Жыл бұрын
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); }
@studyonline3236
@studyonline3236 Жыл бұрын
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
@studyonline3236
@studyonline3236 Жыл бұрын
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]
@RAINING606
@RAINING606 Жыл бұрын
thanks brother
@tori_bam
@tori_bam 7 ай бұрын
I cannot thank you enough for this lesson. Really appreciate for this step by step build ups
@sumitkevlani5740
@sumitkevlani5740 Жыл бұрын
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.
@ajaysaini5314
@ajaysaini5314 Жыл бұрын
#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); }
@Area-fd8ht
@Area-fd8ht Жыл бұрын
​@@ajaysaini5314bhai eska tabulation hai ??
@raghavmanish24
@raghavmanish24 3 ай бұрын
understood .....this time it takes time but finally smjh aa hi gya...thanku striver
@stith_pragya
@stith_pragya 10 ай бұрын
UNDERSTOOD......Thank You So Much for this wonderful video............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
@siddheshpawar2823
@siddheshpawar2823 2 жыл бұрын
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.
@aayush5474
@aayush5474 2 жыл бұрын
that's what i thought too
@takeUforward
@takeUforward 2 жыл бұрын
Yes, you can do that too, takes another N to backtrack if the length is smaller of lis.
@niteshverma8281
@niteshverma8281 2 жыл бұрын
@@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(); }
@Rk-tm8z
@Rk-tm8z 2 жыл бұрын
same
@himanshu6665
@himanshu6665 Жыл бұрын
@@Rk-tm8z best
@realProLog
@realProLog 17 күн бұрын
It took me to watch the last 5 min three times to understand the algorithmic approach implementation.
@keshavbiyani9202
@keshavbiyani9202 4 ай бұрын
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
@arkasarkar3901
@arkasarkar3901 Жыл бұрын
6:17 optimised tabulation , 17:40 -> print lis ,23:13 final code
@tushararora-uv1zp
@tushararora-uv1zp 7 ай бұрын
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 ?
@jonu.1504
@jonu.1504 11 ай бұрын
It can be solved in O(NlogN) using Patience Sorting algorithm
@abc-ym4zs
@abc-ym4zs 10 ай бұрын
How to learn these many algorithms and improve our thinking it really very scary bro
@sayandey2492
@sayandey2492 Жыл бұрын
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
@Zunan263
@Zunan263 2 жыл бұрын
Dp on trees and graphs plz
@sahilgagan2242
@sahilgagan2242 2 жыл бұрын
he did already
@TheDev05
@TheDev05 Жыл бұрын
Similar prob. : 1626. Best Team With No Conflicts
@anuragC819
@anuragC819 2 жыл бұрын
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
@NomanKhanK-IT-
@NomanKhanK-IT- 2 жыл бұрын
me too bro
@deepaktiwari7059
@deepaktiwari7059 2 жыл бұрын
inner loop is for prev as prev can be any index from (currInd - 1 ) to -1 (if their is no prev)
@harpic949
@harpic949 2 жыл бұрын
@@deepaktiwari7059 pata h yaar itna to..par ye utna intutive nahi h
@altafmazhar7762
@altafmazhar7762 2 жыл бұрын
@@harpic949 Bro tabulation intutive hota bhi nhi hai we just do it for auxillary space optimization, only recursive solution are inituitive
@pk4288
@pk4288 2 жыл бұрын
++
@ritikshandilya7075
@ritikshandilya7075 4 ай бұрын
really really awesome approach , thanks for great learning Striver
@keyurraval191
@keyurraval191 Жыл бұрын
Got the same question in my Capgemini test today. Thanks Bhaiya
@gouravanand1749
@gouravanand1749 Жыл бұрын
for which position?
@Area-fd8ht
@Area-fd8ht Жыл бұрын
Doggy style position ke liye😂😂
@gouravanand1749
@gouravanand1749 Жыл бұрын
thanks for sharing your experience👌
@aditithakur6226
@aditithakur6226 Жыл бұрын
Understood Sir. Thank you so much.
@daniyalhussain5231
@daniyalhussain5231 Жыл бұрын
This is the Best DP series but, got to say that this question was the least intuitive one to solve.
@aryansinha1818
@aryansinha1818 2 жыл бұрын
06:03 Alternative Method 17:21 Tabulation Method Code ends - Print LIS Explanation
@aarifhannan4429
@aarifhannan4429 2 жыл бұрын
Most Efficient Code:- #include int longestIncreasingSubsequence(int arr[], int n){ vector lis; lis.push_back(arr[0]); for(int i=1;i
@nikhilsaharan
@nikhilsaharan 2 жыл бұрын
we could also trace our LIS from the previous method: once we have completed making our dp array, we start from location (0,0) in it. Now we check if this index has to be included in the LIS or not. If we are at a location (r,c), we can check this by looking at which one among dp[r+1][c] and dp[r+1][r+1] + 1 is bigger. If dp[r+1][r+1] + 1 is bigger, we include arr[r] and go to the location (r+1, r+1).Else we do not include arr[r] and go to the location (r+1, c). Now we repeat the same process. Here's the python code for it: def printLIS(arr): n = len(arr) dp = [[0 for i in range(n+1)] for j in range(n+1)] for r in range(n-1, -1, -1): for c in range(r+1): dp[r][c] = dp[r+1][c] if(c == 0 or arr[r] > arr[c-1]): dp[r][c] = max(dp[r][c], dp[r+1][r+1] + 1) LIS = [] r,c = 0,0 while(r < n): if(dp[r+1][r+1] + 1 > dp[r+1][c]): LIS.append(arr[r]) r, c = r+1, r+1 else: r, c = r+1, c print(*LIS)
@ajaysaini5314
@ajaysaini5314 Жыл бұрын
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); }
@inderjotsingh5868
@inderjotsingh5868 Жыл бұрын
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--; } }
@pratikshadhole6694
@pratikshadhole6694 Жыл бұрын
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
@pritz9
@pritz9 Жыл бұрын
@@pratikshadhole6694 The elements in the subsequence does not matter, only the order must be maintained.
@ntgrn-pr5yx
@ntgrn-pr5yx Ай бұрын
understood , thank you striver
@Harshit126
@Harshit126 2 жыл бұрын
Understood, respect! The last method could actually be used for Longest Ideal Subsequence also which has been giving TLE eternally :P Thanks a ton!
@yashsinghal3404
@yashsinghal3404 2 жыл бұрын
that space optimization trick using next and prev is dope!
@danishsharma496
@danishsharma496 Жыл бұрын
bro I didnt get that can u tell which video is he refereing to
@lucygaming9726
@lucygaming9726 11 ай бұрын
@@danishsharma496 watch the first video of dp on strings
@Raj-yr3vz
@Raj-yr3vz Жыл бұрын
similar question Longest Arithmetic subsequence
@iamnoob7593
@iamnoob7593 10 ай бұрын
understood the initial tabulation , Thanks
@bose_ofc
@bose_ofc 3 ай бұрын
Last 4 mins ,.. Striver on God Mode
@princepawar5655
@princepawar5655 Жыл бұрын
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-- } }
@tanishkarawat5266
@tanishkarawat5266 5 ай бұрын
Trying all given possibilites on comments, I think the code striver is teaching is best though its not intutive
@ratinderpalsingh5909
@ratinderpalsingh5909 Жыл бұрын
Understood, sir. Thank you very much.
@RaghavSharma-nt3hr
@RaghavSharma-nt3hr 2 жыл бұрын
17:49 - Print LIS Logic
@reggiehurley1479
@reggiehurley1479 Жыл бұрын
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
@itishachoudhary906
@itishachoudhary906 3 ай бұрын
Understood! Thank you sir.
@lakshaysharma6550
@lakshaysharma6550 2 жыл бұрын
UNDERSTOOD!!!!🔥🔥🔥🔥
@UECAshutoshKumar
@UECAshutoshKumar 5 ай бұрын
Thank you Understood!!!
@barshapaul9461
@barshapaul9461 2 жыл бұрын
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 :)
@kankanaki4368
@kankanaki4368 2 жыл бұрын
same
@ganeshkamath89
@ganeshkamath89 2 жыл бұрын
Thanks Striver. Understood.
@siddharth794
@siddharth794 2 жыл бұрын
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
@AdityaKumar-y7g7k
@AdityaKumar-y7g7k 4 ай бұрын
If we optimize 2D array space optimization into 1D array space optimization then the code is almost similar to the code striver explained at 7:00
@cinime
@cinime 2 жыл бұрын
Understood! I really really really appreciate your explanation!!
@prabhakaran5542
@prabhakaran5542 7 ай бұрын
Understood ❤
@immortal6978
@immortal6978 Жыл бұрын
Really challanging for me to make it today >>>
@d_0364
@d_0364 4 ай бұрын
I think we can do it in NlogN + PlogP where P is LIS size
@devbhattdev1607
@devbhattdev1607 2 жыл бұрын
please provide documentation or write ups of the this algorithms please
@Galactushere
@Galactushere 4 ай бұрын
Another approach vector longestIncreasingSubsequence(int n, vector& arr) { // Code here vector dp (n+1, 1); for(int idx = 0; idx
@Ayush-lq3fz
@Ayush-lq3fz 2 жыл бұрын
Hey striver. What is the timeline for the updation of notes. It's not there in the DP notes section.
@imajt5
@imajt5 Жыл бұрын
Hi @3:40 why he has taken dp[ind+1][ind+1] instead of dp[ind+1][ind]
@aakashgoswami2356
@aakashgoswami2356 Жыл бұрын
yes. same doubt
@mohitsingh7793
@mohitsingh7793 2 жыл бұрын
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
@gamerglobe4839
@gamerglobe4839 2 жыл бұрын
it is perfect!!
@anshumaan1024
@anshumaan1024 Жыл бұрын
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 🙂
@GeniuslyTensai
@GeniuslyTensai 2 жыл бұрын
could someone explain the while part. unfortunately i could not understand
@lephanthanhbinh6187
@lephanthanhbinh6187 2 жыл бұрын
always understand the recursive approach so far, but I can't understand why we always can convert it to tabulation. I think recursion is different from having 2 loops nested, can anyone explain to me?
@pranavsharma7479
@pranavsharma7479 2 жыл бұрын
any code written in recursion can be converted to loops, and vice and versa and loops method has benefit in time complexity and space too
@premkamal4790
@premkamal4790 2 жыл бұрын
For recursion we are using auxilary stack space for every function call. So, Inorder to omit the extra space complexity we use tabluation.
@035asadali8
@035asadali8 2 жыл бұрын
even the time complexity of recursive approach and tabulation are same but internally tabulation is faster
@gouravjha4042
@gouravjha4042 Жыл бұрын
Try drawing the recursion tree, and then print the dp matrix of both recursion and tabulation. It's some hard work, but you'll get it once you compare.
@RitikKumar-lv8cm
@RitikKumar-lv8cm 2 жыл бұрын
bhaiya confuse about co-ordinate change please clear doubt
@GungunRamchandani
@GungunRamchandani 5 ай бұрын
UNDERSTOOD
@adityapahujavines3684
@adityapahujavines3684 Жыл бұрын
why are second parameter going in +1 states?
@akshikaagarwal2437
@akshikaagarwal2437 Ай бұрын
Hey! Why are we running the loops in opp direction? Why can't we do it by running them in straight fashion?
@hardikgupta7924
@hardikgupta7924 2 жыл бұрын
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💡
@rohalkurup1350
@rohalkurup1350 2 жыл бұрын
I also have the same doubt, not able to understand how Striver changed it from recursion to tabulation
@kamalphoolwani6075
@kamalphoolwani6075 2 жыл бұрын
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
@pranavsharma7479
@pranavsharma7479 2 жыл бұрын
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
@vivekverma4012
@vivekverma4012 Жыл бұрын
Thankyou @striver
@divyanshugupta5006
@divyanshugupta5006 Жыл бұрын
🔥
@paneercheeseparatha
@paneercheeseparatha 2 ай бұрын
Didn't completely get that state shift approach. Could appreciate more problems involving that. Can you or someone pls suggest any related problems?
@ugthesep5706
@ugthesep5706 2 ай бұрын
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
@paneercheeseparatha
@paneercheeseparatha 2 ай бұрын
@@ugthesep5706 oh ok. thanks!
@SYCOA12CHAITANYAASOLE
@SYCOA12CHAITANYAASOLE 3 ай бұрын
Understood !!
@sanketatmaram
@sanketatmaram 3 ай бұрын
Understood!
@zhunzargulhane6741
@zhunzargulhane6741 10 ай бұрын
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.
@amanmishra-vt8hk
@amanmishra-vt8hk 9 ай бұрын
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].
@sameersahu4569
@sameersahu4569 2 жыл бұрын
Understood!!Thank you
@pratikshadhole6694
@pratikshadhole6694 Жыл бұрын
why hash[lastIndex] !=lastIndex ? As there can be a possibility that at 3rd index hash[lastIndex] is also 3 then at that place it will stop and won't go further
@parvahuja7618
@parvahuja7618 6 ай бұрын
thankyou so so much sir
@sanyamwalia217
@sanyamwalia217 Жыл бұрын
Thanks for that 👍
@shreyatiwari8239
@shreyatiwari8239 4 ай бұрын
can we directly use this tabulation approach in interviews for prev lis question
@mr.cyclotron
@mr.cyclotron 15 күн бұрын
does anyone know why taking reverse order in memoisation, and non reverse order in tabulation doesn't work? why Striver took non reverse order in the memoisation approach?
@36_sachinkumar92
@36_sachinkumar92 Жыл бұрын
Can anyone tell how prev_index start from index-1 in tabulation
@nileshb2471
@nileshb2471 2 жыл бұрын
Great video!! But he did not explain what is being stored in the dp table formed using nested loops. Can anyone please explain?
@aroonimgoswami5775
@aroonimgoswami5775 2 жыл бұрын
ok
@parthsalat
@parthsalat 2 жыл бұрын
ok
@adityavarma1334
@adityavarma1334 2 жыл бұрын
Understood! But the code is giving runtime error.
@balakrishnanr648
@balakrishnanr648 Жыл бұрын
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.
@TanishkPatil-z7u
@TanishkPatil-z7u Жыл бұрын
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
@tot7997
@tot7997 Жыл бұрын
we have used N*N sized array in tabulation also then why it is giving error in memoization only ?
@AdityaSipani
@AdityaSipani Ай бұрын
i dont understad why did he add ind+1 in the second parameter,like how can the prev_ind can be ind+1 and current also ind +1,it should have been ind only if we are considering the take case???
@parthsalat
@parthsalat 2 жыл бұрын
Understood kaka
@shuvbhowmickbestin
@shuvbhowmickbestin Ай бұрын
Can someone please explain to me how both the current and the previous indexes are ending at n-1? Shouldn't the previous be from -1 to n-2?
@georgebell1927
@georgebell1927 2 жыл бұрын
Striver could you please upload the code and the notes for the videos from 38.
@aditi1729
@aditi1729 Жыл бұрын
why are we adding +1 to prev if we're using range -1 to ind-1 in tabulation?
@gururajchadaga
@gururajchadaga Жыл бұрын
because prev's initial value is -1 which is not a valid array index.
@amanmishra-vt8hk
@amanmishra-vt8hk 9 ай бұрын
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 .
@shashankagrawal3171
@shashankagrawal3171 2 жыл бұрын
How to print LIS without using dp? I mean in O(NlogN)..?
@Harshitbejsbsksjnw
@Harshitbejsbsksjnw 23 күн бұрын
at 3:45 why second i+1 in dp[i+1][i+1], please explain as simple as you can, really need help !
@anjaligupta2101
@anjaligupta2101 Ай бұрын
why second parameter in take is ind+1 and not ind?
@shreyash184
@shreyash184 6 ай бұрын
Really definition of previous index is previous index, I think you could have explain that part in a better way !!1
@saunaknandi1814
@saunaknandi1814 2 жыл бұрын
Bhaiya can u teach how to do dfs with memoization?
@ytg6663
@ytg6663 2 жыл бұрын
Dfs already uses stack
@cse-b-132ashishupadhyaya5
@cse-b-132ashishupadhyaya5 2 жыл бұрын
DFS has no overlaping Subsequence ,so no point of using Memoization there!!!!!!
@premduvvapu476
@premduvvapu476 Жыл бұрын
Understood
@Superheroic_Anime
@Superheroic_Anime 2 жыл бұрын
Understood bhaiya !!!
@harshitbhatt6822
@harshitbhatt6822 2 жыл бұрын
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?
@ShlokMansata
@ShlokMansata 4 ай бұрын
Why we cannot start from beginning like we used to do in other problems
@ujjalsaha428
@ujjalsaha428 2 жыл бұрын
As always "understood" ❤️
@saunaknandi1814
@saunaknandi1814 2 жыл бұрын
good
@parthsalat
@parthsalat 2 жыл бұрын
good
@aayushbisht4307
@aayushbisht4307 2 жыл бұрын
good
@amankrsingh
@amankrsingh 2 жыл бұрын
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
@aditikapoor8623
@aditikapoor8623 Жыл бұрын
How does it always gives lexicographically smallest array
@rabiprakashshanitwarangal527
@rabiprakashshanitwarangal527 Жыл бұрын
can you provide the handwritten notes of dp series??
@pulkitranjan8189
@pulkitranjan8189 2 жыл бұрын
is printing LIS asked in interviews I am planning on leaving this
@_hulk748
@_hulk748 2 жыл бұрын
understood sir🙏🙏
DP 43. Longest Increasing Subsequence | Binary Search | Intuition
16:27
DP 41. Longest Increasing Subsequence | Memoization
24:35
take U forward
Рет қаралды 346 М.
Мама у нас строгая
00:20
VAVAN
Рет қаралды 12 МЛН
كم بصير عمركم عام ٢٠٢٥😍 #shorts #hasanandnour
00:27
hasan and nour shorts
Рет қаралды 11 МЛН
When Cucumbers Meet PVC Pipe The Results Are Wild! 🤭
00:44
Crafty Buddy
Рет қаралды 61 МЛН
FOREVER BUNNY
00:14
Natan por Aí
Рет қаралды 34 МЛН
5 Simple Steps for Solving Dynamic Programming Problems
21:27
Reducible
Рет қаралды 1,1 МЛН
2 Years of C++ Programming
8:20
Zyger
Рет қаралды 10 М.
DP 26. Print Longest Common Subsequence | Dp on Strings
16:55
take U forward
Рет қаралды 208 М.
DP 47. Number of Longest Increasing Subsequences
20:46
take U forward
Рет қаралды 119 М.
DP 44. Largest Divisible Subset | Longest Increasing Subsequence
14:39
take U forward
Рет қаралды 127 М.
Мама у нас строгая
00:20
VAVAN
Рет қаралды 12 МЛН