Programming Interview: Longest Increasing Sub-sequence (Dynamic Programming)
Вставка
- Опубліковано 7 лис 2024
- This video lecture is produced by S. Saurabh. He is B.Tech from IIT and MS from USA.
Find the longest increasing subsequence of a given array of numbers using dynamic programming.
C++ implementation code given by Gerald Stan ideone.com/rxsaWK
This channel is an ultimate guide to prepare for job interviews for software engineers, software test engineers, computer scientists, engineering students specially computer science and IT engineers, Master of computer application (MCA) and Bachelor of Computer Application (BCA) students. The content of this channel will help students prepare for C,C++, Java, data structures and algorithms. It also covers courses related to networking and database. This channel can be used by students of NIIT, IGNOU etc too.
To study interview questions on Linked List watch • Programming Interviews...
To prepare for programming Interview Questions on Binary Trees
• Programming Interviews...
To study programming Interview questions on Stack, Queues, Arrays visit
• Programming Interviews...
To watch all Programming Interview Questions visit
• Programming Interviews...
To learn about Pointers in C visit
• Pointers in C (All you...
To learn C programming from IITian S.Saurabh visit
• C Programming Tutorial
"longest increasing subsequence",
"longest increasing subsequence dynamic programming",
"longest increasing subsequence in nlogn"
"longest increasing subsequence dynamic programming ppt"
"longest increasing subsequence dp"
"longest increasing subsequence nlogn"
"longest increasing subsequence algorithm"
"longest increasing subsequence dynamic programming nlogn"
"longest increasing subsequence wiki"
Hey Saurabh,
You have explained a lot of algorithms in a very simple way. Appreciate it.
L(3)=should be 2 as by defination L(i) gives the the length of Longest Increasing Subsequence till ith element.
Superb video helping me to clear out my concept
SUNIL SINGH I agree LS(3) should be 2. But by this formula L(3) is coming as 1. I think the slight modification in the formua should be LS(i)=LS(i-1) if no such j is found.
+SUNIL SINGH how can it be 2 ? it doesn't satisfy both the properties !
I tried many textual tutorials to learn this LIS problem....but this video tutorials really helps me a lot to understand this problem. I really like your way of teaching ...it awesome man.
Suggestion:- A little bit of noise problem in the audio at some points...disturb the flow of understanding.So try to reduce it in your later videos.
rest of all are good. Great Work.
You could change the LS(i) function definition like
LS(i)=max( LS(j) + 1) for all j>=1 && j
Thanks a lot sir, this is the best explanation of the 'Longest subsequence problem' on the internet. Your videos are really helping me for my Algorithms course.
Saurabh, thanks for sharing these videos. I'm very grateful to you. All videos are easily understood.
sir,the effort with which you have explained is really appreciable.your explanation is also superb.
Great explanation Saurabh........specially the example....... even our Caltech professor could not break the web in lecture
Excellent Saurabh. You explained it clearly in very simple terms. Thumbs up!
Thanks varun, I am very glad that you liked the videos and that they are helpful
Great video, helped me out a ton for my algo class at Georgia Tech! Thank you!
You are welcome Kemble!
saurabhschool Hi Could you also provide with the code which we can see? would be of great help if you can. :)
9:41 probably a fly was there near your microphone. :D
i think you should take care of the last element, if it lesser then all the previous elements, your answer reduces to 1, which is a wrong solution. I think you should make a special check, if its the last element, the ans will be max(1+LS(j) if there exists a j such that A[j]
Very neat explanation of getting the longest sub sequence length, However, How do we retrieve the sub sequence it self? so we shud get both the length and the sub sequence by the end of the algorithm.
Such a neat explanation ,extraordinary ,brilliant many many thanks for helping the learners.
It would be better if u also provide Java code implementation also
for all the problems. Keep up the good work. God Bless u.
HI saurabh...
your explanation is so good...if possible plz cover EDIT DISTANCE problem also...
very nice...very infomative. I would love to see more of these videos.
That was really helpful for preparation of my coding interviews. Thank you very much.
You are welcome Rohan
very nice explanation sir. Pseudo code will be a great help too.!
Thank you Saurabh! Great video :)
Thanks .....good explanation
keep more videod from introduction to algo.......chapter 17 ......amortized analaysis and haffman code
taking course.....and your explanation is helping me alots
The final answer is not LS(8). The correct answer is the maximum element of the LS array. Here in this example LS(8) is the largest element. So it seems that the answer is LS(8). Try with the input {10,22,9,33,21,50,41,60,20}. You would know the difference. By this input LS(8) will be 2 which is not actually the answer but the correct answer is 5 which is also the maximum element in the LS array.
There is something missing. In the example you have taken, if the last element is 1, then according to your algorithm, the answer will be 1, when it should be 6. I think that you should save all of LS(i) and after the computations, find the largest element among it and then print it.
everyone saying "great explanation, well done!" but I don't think so: this was a magical, hand-wavy "explanation" that doesn't show how you actually do the max{LIS[j]} part which requires memoization, recursion, or a table as usual DP problems. There are better explanations on youtube, including actual code.
Hello Sir is it not possible to solve using Knapsake way to solve?
hiee.. Actually i was looking for a good dynamic programming tutorial ...Luckily i found this.. Thanks a lot ....I didnt go through all ..But I want to know whether You have any java implementation of this ..... Thanks in advance
hi Saurabh, nice video, but for that example, what if the sequence is 10,22,9,33,21, so LS(5) = 2, which is 10,21 or 9, 21, but actually longest is 10,22,33, right?
Hi, LS(5) is length of longest sub sequence with a[5]=21 as last element of sequence and LS(i=n=5) is not always the solution to problem.Solution is Max{LS} (Saurabh should have mentioned this in video) which is LS(4) in this case, you are right !!
Really a great explanation.. don't give up on your teaching (y)
Thanks Jaya for your nice comment. I would take your advice and keep making more video lectures
Great explanation. I loved it.
You explained it very clearly. THX!
Really good explanation. Thanks!
This is correct solution but complexity is O(n^2) . It can be done in O(nlogn)
i am becoming fan of your articles.. have seen many till now. here i request you write the article on " Ford-Fulkerson Algorithm for Maximum Flow Problem" .
Ok Sumit, I will make one lecture on Ford Fulkerson Max Flow
Great explanation sir!!
thanks Kaustav for your compliment
I understand your algo but i want to print out the longest subarray instead of number of elements in that array. what should i do?
Thx! Mr.Saurabh!
Thanks for explaining it so clearly.
the example you show is helpful, thx man
Can you explain how we get the answer in O(nlgn) time? Would be really good
Good explanation but I think it would be better if you represent it a bit more visually alongwith the equations.
saurabhschool also you must stress the need of (memoization) using an array to store the value of LS(i) computed in order to avoid recalculation of same problem. as you have already shown in LCS problem.
And I thought Dynamic Programming was tough :P ...Awesome explaination. Would be very helpful if after every concept you could just twist that a little bit and serve us :)
It looks like your algorithm just finds the length of the longest increasing subsequence. Why not save the values that make up the longest increasing subsequence also so that you can return it along with the length?
Amazing explanation
Superb..!!
is the code available anywhere?
Nice lecture................
Welcome Nikita!
you are most welcome :)
very well explained.
Great example !!! :)
thx alot. I enjoyed a lot
excellent thanks a ton
Never listened to u in classroom .Realised what I missed :/
great video!!! thank you
why 7,8,12 is not increase subsequence
sir how ls(3) = 1??
because
LS(i) = 1 + max(LS(j)) for such j a[i]
= 1 if no such j found
here NO SUCH j was found hence it is 1.
thank you! helps!
welcome Mr sup boy
the end of the answer is wrong. you repeat LS(7) twice, so at the complete bottom of the screen it should say LS(8) but you call it LS(7). you should also finish on LS(9), but you finish on LS(8) because you repeat LS(7).
LS(7) is repeated
not a good tutorial. You need to work more on lecture dilivery skills.