Longest Increasing Subsequence

Given an array find longest increasing subsequence in this array.

[atishnarlawar]

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!

[Autom_te]

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!

[alfonsovalenciana]

After all these years, I still come back to this channel. Always loved the clear way you explain!

[souvikghosh]

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.

[anamigator]

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.

[treksis]

This video is made 6 years ago and still one of the best

[slowmotion]

No fancy animation, no BS music and intros, 100% explanation, You make it look like it's a piece of cake.

[vikremsheker]

Excellent explanation ! Thank you for taking the time to make these videos !

[abnormal]

@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.

[SubhamKumar-egpw]

Struggled whole day on a problem on alternating sequence. Then solved within 15 minutes after watching this. Thanks a lot :)

[RakeshGajjar]

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!

[slizverg]

Wow, that’s the first video on that subject there I finally understand the algorithm! Many thanks!:)

[Chelsea_Alexis]

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.

[eduardopetry]

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)

[gajju]

first time I found best video of LIS question.
thanks from bottom of my heart!

[jeremyedbert]

Thank you so much for making this video easy to understand. Keep going on!

[ffles]

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!

[lalitdudheria]

We need more people like you Tushar. I have seen many of your videos. You explain really well :)

[weijiang]

Thanks for your sharing ! If only I had seen it earlier 😭！

[karthikmucheli]

yes, we will have to use DP to solve this problem. :D:P