Its worth to appreciate the hard work. Any one can easily see him so exhausted after doing the daytime job at Apple. But he still makes these helpful videos. Kudos!
Intuition behind this solution: If the current element is greater than the previous element, we can safely add 1 to the value of previous max sum. Since the previous max sum was also calculated in a similar manner (optimal substructure) we can safely add 1 to previous max value to get the current value. If you notice in case of 6, since it is greater than 0, you can add 1 to the max value at 0. But there is a catch, you can have previous elements (for example 4) which can give you a bigger subsequence. Hence to check this, every time the "j" begins with zero. Or you can even start at the given i and keep going backwards with a j variable to check if there are two or more contending elements which can give you the max value. Notice how we construct the solution from using the previous solutions (previous values in array). This is in essence Dynamic Programming where you remember the previous computed values and make calculations faster. PS: please correct mistakes if any.
For people who don't have much time to watch the entire video here is the solution 0:45 --> "Yes we will have to use dynamic programming to solve this "
There is a small optimization here (Not talking about DP):- Rather than starting j from index 0, start j from i-1 and then go backward. what difference will it make? see below: If let's say you're at index i = 500 Then you move from j=499 and at j=300 you find that its LIS is 200 and array[j] is lesser than array[i], then you make LIS of i=500 as 200+1 = 201. Now when you continue going backward i.e j=299,298,297.......then you do not need to go beyond j=200 because you already know that those elements can have LIS as 200 at max, So no need to compare.... This would save your 200 iterations which you had to do when you were starting j from 0 index.
Great video! I wrote a function in Python that implements the algorithm Tushar exposed in the video. Hopefully this helps someone better understand how it works... def LIS(arr): j, i, t = 0, 1, [1] * len(arr) # initialize ints j, i and array t while i < len(arr): # loop while i is within the sequence's bounds if arr[j] < arr[i]: t[i] = max(t[i], t[j] + 1) # exact same logic Tushar wrote at the end of video j = j + 1 # at each iteration, increment j if j == i: j, i = 0, i + 1 # if j meets i, set j to 0 and increment i return max(t)
Thank you so much for this video. The simple fact that you stepped through the algorithm was what I needed to understand what was going on. I don't know why so many teachers skip it!
I agree that explaining the recursive or iterative brute force method first would be better. Doing so would help with making the connection from how you would solve the problem naively, to how you could use dynamic programming to solve it faster
This is the recursive solution def li_seq(arr): if not arr: return 0 if len(arr) == 1: return 1 count = 0 for i in range(1,len(arr)): end_at_i = li_seq(arr[:i]) if arr[-1] > arr[i - 1]: count = max(end_at_i + 1, count) return count
he wont do this cuz solving this problem by recursion it would take too much, just imagine that if u give a super long subseqvence it can take up to some months for your computer to find the solution, the best 1
Additional fact: To backtrack all you need to do is to maintain a separate array of size N, which stores the "j" for which the "i"th index was last updated. Then when you get the maxima in the original array, just search for the index of j recursively, until you reach a number which has the value of 1 in the original array
Excellent videos!Great going..I haven't seen such wonderful videos with clear explanation.Only through your videos i came to know clearly what dynamic programming actually means. Still that i couldn't understand anything just i thought we need to build a 2D array by your video only i came t know how the principles of dynamic programming are satisfied.Keep posting videos.
I like that you put the word Length at the end of LIS. It is stating that you completely understand it. Finding the length instead of the actual LIS itself was confusing me a lot!
The recursive approach according to me:- 1. Iterate through the array containing the sequence. 2. We will have two options either we can select the first element or not. 3. Now if the next element of the array is greater than the previous element we will again have two choices either we can select the element or not.
at 02:42, why would the value at -1 be 1 ? shouldn't it be 2 ? because the value represents the length of the LIS up until that point. so up until -1, LIS would be of length 2 containing 3 and 4.
It represents the longest increasing subsequence up until that point including the value in question. It's necessary because when you do the comparison later, you need to know the maximum value up to that point. If we set the value at -1 to 2, then a later 0 or 1 would give us a subsequence of 3, which isn't actually true because the full subsequence doesn't contain a -1. For example, if you walk through the algorithm like you described, we would have a longest subsequence value of 3 at value 0, and 4 at value 6.
the index below shows `the LIS about the current number`, instead of `globally longest`, i.e. let's consider the number `6`, we have LIS: 3,4,6, when we check the 3, we add 1 to index of 6, when we check the 4, add 1 again, this process means that `we found at most 3 lengths increasing seq including 6 itself, after we launch this process for all the number, we can find the longest seq by checking the length index
It represents Length of subsequence using elements till that index and *including* that element in the subsequence. So if we include -1 in subsequence, we get {-1} as subsequence.
bro thx a lot.. most of the youtuber now a days just focus on learning the dp and do recursive solution then convert into dp (tabulation) just follow the prewritten steps by some youtuber.. they don't understand, how amazing the tabulation is..
Really really great explanations, thank you very much. Just one suggestion : I thoroughly understood the solution but still I don't know the intuition behind coming up with this solution. Could you please explain that also? Oh And the time complexities as well. thanks again :) :)
The intuition here is like an eye ball movement. Let's say you have a simple array [1,2,4]. The answer is 3. How ? In the eyeball movement you see the number 1 then register in your brain 1 . When you go to the next number 2, your brain takes the previous value from your brain which is 1 and add 1 more to it and store it back to 2 in your brain. Same thing when you move your eye to 4. Take the previous value from your brain which is 2 and add +1 which is the final answer (3). Here we lay down our brain as one dimension array. The default value is 1 that mean if you select any number randomly the answer is 1. E.g. [12,4]. If I choose 12 from my eye ball it is 1 or if I choose 4 also the default value is 1. The process of incrementing 1 from previous array value is same as reading the existing brain content and add 1. This is the thumb rule of knapsack problem. You keep updating your brain with the best increasing value by erasing the old content and update the new content. Same here we do select the maximum value of the current value or the previous value +1. Eventually any DP tabulation problem is just converting the eyeball movement calculation into array layout. Hope this helps you. Thank you!!!
I have one suggestion. Before solving any DP problem, please first solve it with recursion then only move to DP. This will help us in better understanding of the problem and why is the need of DP here.
Its worth to appreciate the hard work. Any one can easily see him so exhausted after doing the daytime job at Apple. But he still makes these helpful videos. Kudos!
This example was so clear and easy to follow that I can only wonder _how_ my professor did such a bad job at explaining this. Thank you!
After all these years, I still come back to this channel. Always loved the clear way you explain!
No fancy animation, no BS music and intros, 100% explanation, You make it look like it's a piece of cake.
Intuition behind this solution:
If the current element is greater than the previous element, we can safely add 1 to the value of previous max sum. Since the previous max sum was also calculated in a similar manner (optimal substructure) we can safely add 1 to previous max value to get the current value.
If you notice in case of 6, since it is greater than 0, you can add 1 to the max value at 0. But there is a catch, you can have previous elements (for example 4) which can give you a bigger subsequence. Hence to check this, every time the "j" begins with zero. Or you can even start at the given i and keep going backwards with a j variable to check if there are two or more contending elements which can give you the max value.
Notice how we construct the solution from using the previous solutions (previous values in array). This is in essence Dynamic Programming where you remember the previous computed values and make calculations faster.
PS: please correct mistakes if any.
He is such a gem of a person. I don't know why he has stopped making such videos now. Wish he comes back again.
For people who don't have much time to watch the entire video here is the solution
0:45 --> "Yes we will have to use dynamic programming to solve this "
Struggled whole day on a problem on alternating sequence. Then solved within 15 minutes after watching this. Thanks a lot :)
This video is made 6 years ago and still one of the best
Yes..I'm having 3rd semester now😄😨
yea it so crazy. 8 years later, I watched like 10 newer videos yet this is still the best explanation.
There is a small optimization here (Not talking about DP):-
Rather than starting j from index 0, start j from i-1 and then go backward. what difference will it make? see below:
If let's say you're at index i = 500 Then you move from j=499 and at j=300 you find that its LIS is 200 and array[j] is lesser than array[i], then you make LIS of i=500 as 200+1 = 201. Now when you continue going backward i.e j=299,298,297.......then you do not need to go beyond j=200 because you already know that those elements can have LIS as 200 at max, So no need to compare.... This would save your 200 iterations which you had to do when you were starting j from 0 index.
Excellent explanation ! Thank you for taking the time to make these videos !
All your videos are excellent, extremely Helpful.
Great video! I wrote a function in Python that implements the algorithm Tushar exposed in the video.
Hopefully this helps someone better understand how it works...
def LIS(arr):
j, i, t = 0, 1, [1] * len(arr) # initialize ints j, i and array t
while i < len(arr): # loop while i is within the sequence's bounds
if arr[j] < arr[i]: t[i] = max(t[i], t[j] + 1) # exact same logic Tushar wrote at the end of video
j = j + 1 # at each iteration, increment j
if j == i: j, i = 0, i + 1 # if j meets i, set j to 0 and increment i
return max(t)
I stugled to understand this problem and referred other sources as well. This video gave me a final push to clear my understanding. Thanks Tushar!
Thank you so much for making these helpful videos!! I watched this whole playlist before my dynamic programming exam and I got an A on it.
yes, we will have to use DP to solve this problem. :D:P
XD
staaahpp!!! 😂
Actually a better solution is to use binary search, the time complexity becomes N logN, but its good to know DP
Wow, that’s the first video on that subject there I finally understand the algorithm! Many thanks!:)
We need more people like you Tushar. I have seen many of your videos. You explain really well :)
Thank you so much for this video. The simple fact that you stepped through the algorithm was what I needed to understand what was going on. I don't know why so many teachers skip it!
@Tushar: Just a suggestion, it would be great if you can solve it using recursion first and then explain as how this problem falls into DP category.
u are right
I agree that explaining the recursive or iterative brute force method first would be better. Doing so would help with making the connection from how you would solve the problem naively, to how you could use dynamic programming to solve it faster
I dint find one video or good article, explaining recursion solution :(
This is the recursive solution
def li_seq(arr):
if not arr:
return 0
if len(arr) == 1:
return 1
count = 0
for i in range(1,len(arr)):
end_at_i = li_seq(arr[:i])
if arr[-1] > arr[i - 1]:
count = max(end_at_i + 1, count)
return count
he wont do this cuz solving this problem by recursion it would take too much, just imagine that if u give a super long subseqvence it can take up to some months for your computer to find the solution, the best 1
This video is the definition of precise.
Thanks a lot for explaining in the simplest way.
first time I found best video of LIS question.
thanks from bottom of my heart!
Thank you so much for making this video easy to understand. Keep going on!
Thank you, algoexpert explained it in 1 hour and it was still not clear as yours!! Cheers thnx👍
lmao never buy algorithm courses
just use geeksforgeeks or hackerrank, its wayy better and covers more stuff. Maybe not systems interview stuff but still
Thank you, sir. We need people like you.
thank you for this video this helped me in my upper div Data Structures class in university for a quiz.
Thanks for your sharing ! If only I had seen it earlier 😭！
Additional fact: To backtrack all you need to do is to maintain a separate array of size N, which stores the "j" for which the "i"th index was last updated. Then when you get the maxima in the original array, just search for the index of j recursively, until you reach a number which has the value of 1 in the original array
Great, I was trying hard for 2 days to understand the algorithm by code. It became simple once I saw this video.
All your videos are true awesome. Thank you a lot Tushar.
your tutorials makes things quite easy..
@Tushar You are awesome man , dp was a real pain for me, after seeing your videos, I am so comfortable, keep up the great work!!!!
thank you for videos... I regularly refer you video tutorials, the explanation is really simple yet clear..!
Awesome explanation!
Far better than the one of GeeksForGeeks
wao very good TUshar ... Simply Amazing
Watched several your videos and subscribed. So helpful that I wish I found you earlier.
Excellent videos!Great going..I haven't seen such wonderful videos with clear explanation.Only through your videos i came to know clearly what dynamic programming actually means. Still that i couldn't understand anything just i thought we need to build a 2D array by your video only i came t know how the principles of dynamic programming are satisfied.Keep posting videos.
I like that you put the word Length at the end of LIS. It is stating that you completely understand it. Finding the length instead of the actual LIS itself was confusing me a lot!
The recursive approach according to me:-
1. Iterate through the array containing the sequence.
2. We will have two options either we can select the first element or not.
3. Now if the next element of the array is greater than the previous element we will again have two choices either we can select the element or not.
no because its not guarenteed that next element itself would contribute to the ans
Great! Better than all the verbose literal explanations all over the Internet
Nice explanation, subscribed after watching first video of this channel, thanks
Thanks Brother!!..Very Nice and clear explanation!!
at 02:42, why would the value at -1 be 1 ? shouldn't it be 2 ? because the value represents the length of the LIS up until that point. so up until -1, LIS would be of length 2 containing 3 and 4.
same question ... Anyone can explain why?
It represents the longest increasing subsequence up until that point including the value in question. It's necessary because when you do the comparison later, you need to know the maximum value up to that point. If we set the value at -1 to 2, then a later 0 or 1 would give us a subsequence of 3, which isn't actually true because the full subsequence doesn't contain a -1. For example, if you walk through the algorithm like you described, we would have a longest subsequence value of 3 at value 0, and 4 at value 6.
the index below shows `the LIS about the current number`, instead of `globally longest`, i.e. let's consider the number `6`, we have LIS: 3,4,6, when we check the 3, we add 1 to index of 6, when we check the 4, add 1 again, this process means that `we found at most 3 lengths increasing seq including 6 itself, after we launch this process for all the number, we can find the longest seq by checking the length index
It represents Length of subsequence using elements till that index and *including* that element in the subsequence.
So if we include -1 in subsequence, we get {-1} as subsequence.
become fan of yours!! watched most of the videos , superb explanation !!
Thanks tushar for explaining so nicely
bro thx a lot.. most of the youtuber now a days just focus on learning the dp and do recursive solution then convert into dp (tabulation) just follow the prewritten steps by some youtuber.. they don't understand, how amazing the tabulation is..
Actually the best video among similar ones.
Tushar, thank you! Very good explanation!
great explanation Tushar
this is the O(n^2) solution but in GFG is it mentioned to solve in O(nlogn).
Awesome explanation... Thanks and keep up the great work
Great job. Thanks for such a great explanation.
Brilliant. Love you man.
Excellent bro.. keep up the good work.
Great work! Thanks a lot for sharing this!
You are a great teacher, sir. Solved my doubt so easily.
great sir, the way you have explained is awesome, keep it up sir 🙂🙂👍👍👍👍
Excellent illustration and demonstration. It would be perfect if you can save candidate sub-sequences simultaneously.
Fantastic explanation and video!
Thankyou so much for these amaxing videos
wow great explanation....very easy to catch
awsome!!!!! Was stuck at this since long time seriously.. Thanks bro
Really really great explanations, thank you very much. Just one suggestion : I thoroughly understood the solution but still I don't know the intuition behind coming up with this solution. Could you please explain that also? Oh And the time complexities as well. thanks again :) :)
The intuition here is like an eye ball movement. Let's say you have a simple array [1,2,4]. The answer is 3. How ? In the eyeball movement you see the number 1 then register in your brain 1 . When you go to the next number 2, your brain takes the previous value from your brain which is 1 and add 1 more to it and store it back to 2 in your brain. Same thing when you move your eye to 4. Take the previous value from your brain which is 2 and add +1 which is the final answer (3). Here we lay down our brain as one dimension array. The default value is 1 that mean if you select any number randomly the answer is 1. E.g. [12,4]. If I choose 12 from my eye ball it is 1 or if I choose 4 also the default value is 1. The process of incrementing 1 from previous array value is same as reading the existing brain content and add 1. This is the thumb rule of knapsack problem. You keep updating your brain with the best increasing value by erasing the old content and update the new content. Same here we do select the maximum value of the current value or the previous value +1. Eventually any DP tabulation problem is just converting the eyeball movement calculation into array layout. Hope this helps you. Thank you!!!
Thanks dude keep doing these kinda videos..
Tushar, you are the shit. Couldn't get through DP w/o you.
+Mike S. he's awesome!
The of explaining is owsm ❤️
Excellent solution! Thank you!
Outstanding explanation!
great explanation, keep up the work
thank you so much Tushar Sir
Good working example! Thank you.
Dude you just killed it !! Awesome explanation !!
excellent explanation.
thank you very much
I'm in Love with this Video and its Explanation.
hi tushar. using 2D like longest increasing palindrome is much simpler. and this approach allows back tracking to print out the actual numbers.
No better explanation exists! perfect!
Thank you. It’s so helpful.
This is awesome, thank you sir 😍
great video, thank you!
explanation couldnt get any better.
Nicely explained !
Thanks Tushar, for sharing this knowledge!
Im out of words, i couldn't find a solution to this problem on my own
Thanks a ton man ! Super helpful !
very nice explanation
What it is the best, worst and average case?
I have one suggestion. Before solving any DP problem, please first solve it with recursion then only move to DP. This will help us in better understanding of the problem and why is the need of DP here.
You are a legend.
Thank you , good explanation.
Gazab explanation
very nice tushar :)
Wouldn't your solution be O(n^2)?
It is , he explains a O(n log n) in another video
Could you tell me which video for O(n log n) ? Thanks!
th-cam.com/video/S9oUiVYEq7E/w-d-xo.html
yes
Bhai DP laga le ab to ...concept to samajh aa hi gya na
You're awesome. Keep up the good work :)
sir ji great explanation
Nicely Explained. Like it very much. In any of your videos, is it explained with O(N Logn N) complexity?
It felt as though you came running and were out of breath when u started the video!
very nice solution, thanks!
The OG DSA wala bhaiya
Great explanation :)