DP 47. Number of Longest Increasing Subsequences

[@takeUforward]

A small correction, LIS till 6 will be length 2 with count 4, and not 5.

[@pranav9653]

How many more video are there in these playlist??

[@shaswataraha7124]

Why not lis till 6 will be length 2 I think it will be of length 3 and its count should be 4

[@Superheroic_Anime]

@@shaswataraha7124 you are right maximum length of lis ending till 6 will be 3
Example 1,2,6
But not a problem small mistake although intitution is very good😁

[@sagarmittal8627]

@@pranav9653 till DP-60

[@sameersahu4569]

Thank you for the correction..i had a doubt regarding that stuff...

[@dropshotOP]

On point explanation!!
One small correction for explanation part: LIS of value 6 is 3 with count 4 {(1,5,6),(1,4,6),(1,3,6),(1,2,6)} and LIS of value 7 is 4 with count 4 {(1,5,6,7),(1,4,6,7),(1,3,6,7),(1,2,6,7)}.
Keep posting more such videos ❤️

[@takeUforward]

Thank you :)

[@aditheorigin4926]

Yes Prasad, but very nicely explained @TakeUForward. Kudos.

[@techspecstm7032]

Please pin this comment!! I wasted what is going wrong for 1hour

[@arnabdutta4662]

pin this comment so that every one can see it
:)

[@praveend3348]

@@takeUforward bro could you please add a note during that calculation, so we don't get confused.

[@abhishekgupta1471]

Thank you so much for this series. There was a time when I was scared just listening to the name of dp but thanks to you now it is now the most interesting topic for me. You developed the confidence in me to tackle dp problems. Thank you so much Striver!!

[@rajat_singla]

If you want to verify, this is how the solution should look:
array: 1 5 4 3 2 6 7 10 8 9
length: 1 2 2 2 2 3 4 5 5 6
count: 1 1 1 1 1 4 4 4 4 4

[@kms8320]

++

[@pk4288]

Wrong count array should be : 1 1 1 1 1 4 4 4 8 8

[@thomasshelby6780]

@@pk4288 you've clearly made a mistake

[@piyushjain6909]

@@pk4288 no

[@tushar_kesharii]

@@pk4288 no , he wrote the Right count array .

[@khanakpatwari2587]

TIP: skip the dry run of first example to save yourself from confusion for the next hour :) . Directly jump to example 2's dry run

[@khushalkumawat2254]

example 2's dry run is also wrong

[@sarthakbehera8324]

@@khushalkumawat2254 not wrong

[@anonymousvoid6356]

thanks for saving my time

[@JoyAcharyatvl]

I wan unable to understand this problem without this lecture. Thank you for this lecture.

[@subhajitdutta5216]

Bhaiya ek video bana do ki how to take a good random example for dry run while explaining my code in an interview

[@sonit9707]

Use your 🧠

[@sameersahu4569]

Completed LIS..on to the next ones....Thank you for this amazing series

[@raghavmanish24]

thanku striver ......finally ye bhi complete kr liya .....very close to finish this extra ordinary dp series .....thnaku thanku thanku striver

[@rittwickbhabak7348]

Understood, Thank You striver, now I am very comfortable in the LIS patter. Thank you very much.

[@durgaprasad-gn4dk]

I understood the complete series. And I am confident about the LIS questions. Thank you for the explanations and the videos.

[@amanpatel8575]

Understood LIS Type from DP series. Thanks a lot Striver for making this series.

[@stith_pragya]

UNDERSTOOD......Thank You So Much for this wonderful video.......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@SahilThakur26]

Bro got super excited and made a mistake during explanation :) This is the first video of the series which i have to watch twice to understand :) . BTW thanks for all the lectures.

[@shalabhbhatiya2146]

yes i bit confuse then i realised that its his fault

[@sahilrepuriya3205]

Understood! i am now falling in love with your teaching style💙

[@shuvo9131]

1, 1, 1, 2, ,2 , 2, 3, 3, 3 ans=27
simulate the testcase and you will find why cnt[ i ] += cnt[ j ] is used.

[@parthsalat]

Maybe you don't realise what you just did.
YOU SAVED MY LIFE!
Due to the mistakes striver made in the first example of this video, I was going to commit suicide. I had the chair, rope and fan ready. But then I came across your comment, did a dry run of the test case, and I was enlightened.
Thanks a lot, keep saving lives!

[@alisaquibraza6870]

@@parthsalat xD

[@devendrapratapsingh6636]

UNDERSTOOD. Also a special thanks to the comment section for the help.

[@shivamsharma-oi3gn]

Dry run this : [34,-45,23,45,76,98,23,100] input, your mind will get boom FOR SURE!💥

[@adarshanku7988]

Pretty much comfortable on LIS. Thank you.

[@nilimsankarbora5911]

Understood LIS Type from DP series. Thanks a lot Striver for making this series. ❤❤❤

[@komalyadav5599]

Understood!! This playlist is very helpful.

[@ritikshandilya7075]

Thankyou for amazing series Striver

[@Blackhawk_9]

Blessed to have ur channel bhaiya❤

[@ritikshandilya7075]

Thanks for amazing thought process Striver

[@ntgrn-pr5yx]

THANK you striver, Understood

[@shrishrajgupta1689]

12:40 dp[j] + 1 > dp[i] *correction

[@shreyaagrawal8916]

I think except LIS all other parts of DP were explained well. This part is a bit confusing.

[@adeshkumar1728]

same for me also

[@kaustubhgaikwad2562]

True

[@kaustubhgaikwad2562]

Striver is good only for Graphs

[@adarshjain-wc9zv]

Thanks Feeling confident about LIS

[@shrishtysingh1853]

best explanation ever!!!!

[@Abcd-jt1qs]

Understood Striver! Thank you so so much :)

[@arnabsarkar5245]

Understood bhaiya.

[@shreyash184]

There is only one mistake in the video and which hampers the complete understanding of this question !!! Will refer some other video, Thanks for the content

[@simranvedpathak7112]

True

[@OnstreamGaming]

Understood sir , hats off

[@shinewanna3959]

Subscribed, u are really great, the reteriving focus from us is the best, best and clear explaination that I ever seen

[@KeigoEdits]

Did it on my own, Understood and thanks :)

[@UECAshutoshKumar]

Understood!!!
Thank You!!

[@dhaya_98]

Bro teaching wrongly but confidently 💪

[@harshi993]

😂

[@harshi993]

Jokes aside he corrected it later

[@lakshmand8413]

Very well explained

[@chinu_.16]

Understood , solved without watching the video you are the besttttttttttt

[@twinklelight9829]

i have understood this series thank you striver

[@hardikarora684]

Thanks striver for this amazing series and also for this question as threre are less variation of lis available on youtube
Kudos

[@prabhakaran5542]

Understood ❤

[@saurabhsangam2737]

Python Solution:
def solution(nums, n):
dp, count = [1] * n, [1] * n
ml = 1
for i in range(n):
for prev in range(i):
if nums[prev] < nums[i]:
if dp[prev] + 1 > dp[i]:
dp[i] = dp[prev] + 1
count[i] = count[prev] # inherit
elif dp[prev] + 1 == dp[i]:
count[i] += count[prev] # increase the combination count
ml = max(ml, dp[i])

ans = 0
for i,l in enumerate(dp):
if l == ml:
ans += count[i]

return ans

[@mudavathsrikanth1944]

Thank you so much for this series.

[@saurabhtiwari9614]

understood bhai ... u teaches absolutly well sir

[@anmolagarwal5950]

Heavenly explanation!!!

[@kumarpurushottam632]

Understood Thank You Striver❤

[@XLR8_Aatma]

Understood very well😊😊

[@GopiPandu1911]

understood LIS pattern🤩

[@bhupeshyadav9957]

bhai ne ek hi jacket mein puri series bna di

[@LBK3]

understood ❤

[@ujjwalprakash9899]

Thanks Striver

[@verma_jay]

understood

[@RohitKumar-dy2gc]

u made LIS so easy😎

[@ratinderpalsingh5909]

Understood, sir. Thank you very much.

[@aayushranjan3675]

Sir, The LIS ending at 6 should be of length 3 and not 2

[@mohaimenchowdhury]

Yes that part is confusing me every time

[@tempaccnt9128]

Hi, thanks for helping each of us and sharing your valuable knowledge.
Can you also make some short videos that will be helpful for revision of basic concepts, common problems, applying DP/DSA in daily life to relate problems?

[@bkumar7380]

amazing
series

[@we_crood]

if u have watch his graph series where we need to calculate the no of ways . you can understand how he uses

[@girishbhargava6367]

Striver, shouldn't the length of LIS till 6 should be 3, since {1 , 5 , 6} , {1 , 4 , 6} , {1 , 3 , 6} and so many other subsequences can be added. You have written 2 in the dp array. Please tell if I am thinking correct.......

[@vipulmaheshwari2321]

Yes you are. He did that by mistake.

[@nookalareshwanth1785]

Yoooo Great videso :0

[@arihantjammar8888]

Understood 😊😊😊😊

[@prashantgoswami5321]

Thank you sir for making this type of question so easy👏👏

[@SahilAli-uq7ym]

Understood 👍

[@pragneshamadavadi2267]

Great explanation 🔥

[@NoBakwas]

Thank you !! :)

[@raushankumar6993]

Yes I can✌

[@akashpal7748]

Understood

[@preetmhaski6317]

Plz explain Binary search O(nlogn) approach for this problem.

[@aagamjain2131]

Unearthly explanation 🔥🔥
Understood
💯💯

[@adityaagarwal2324]

Nicely explained bro ❤

[@adebisisheriff159]

Thanks Bhaiya!!!!

[@energy_00]

I understood👍

[@amankrsingh]

Understood, very comfortable

[@mayanksingh603]

understood

[@ganeshmula4508]

understood sir

[@harshbhardwaj2379]

As always understood . Great explanation sir. Thank you

[@malharnimavat7676]

Nice series

[@rishabhgupta9846]

understood,great explanation

[@modhugumudiushasri2330]

Well understood Sir

[@pulkitjain5159]

currently i am on 12:50 but not getting the intution till yet , i think what bhaiya is doing may be wrong but kuch itna samajh aya ki count for any value will be that na ki use chote bande dhoodho , unme se jiska maxTillYetLIS jitni baar occur karega wahi unka count hojayega , i mean for value 6 , the maxTillYetLis occured 4 times so Lis for 6 will be 3 but count will be 4 , kyuki abhi tak jo maximum lis chalta ara hai unme hi toh naya number add karenge honge unme hi toh add karoge. similarly , ab 7 ke liye maxTillYetLIS sirf 6 pe occur kiya and count for 6 is 4 only toh in charo me 7 jodd denge. now suppose kisi value ke liye maxTillYetLIS do baar occur kara hai aur dono pe hi unka count 4 aur 4 pada hai i mean ki array lelo {.............., 8 , 7 , 9} inse peeche 8 , 7 , 9 se chote numbers hai 8 ko include karke lis kuch banra hai aur count bhi kuch banra hai similiar 7 ko include karke lis kuch banra hai aur count kuch banra hai toh 9 pe kitne banege ? , offcourse count of 7 + count of 8 na kyuki tum 7 tak ke maximum ke aage 9 jod sakte ho aur 8 tak ke maximum aage 9 jod sakte ho aur koi option do dikhta ni , toh simple count m dono ka add kardo.

[@niyammuliya5787]

understood the all LIS varients.

[@chandrachurmukherjeejucse5816]

Great lecture striver. As always "Understood"

[@DevashishJose]

Thank you, understood.

[@sparshbarolia1556]

[@santoshb7776]

Understood sir 🙏🙏

[@adityasaxena6971]

Understood Sir

[@coding8000]

US, understood, thanks man,.
Video is getting blurred in between.,, anyone else ?

[@manthenanagendra1077]

what an energy sir loving the series

[@mohitsingh7793]

If u come from a CP background then is very habitual to understand the intitution very easily.Otherwise it is very difficult to understand it at a very first time.

[@pawanchandra9193]

loved this

[@samridhigarg3489]

Amazing videos, step by step approaches

[@VinayKumar-ze2ww]

Amazing video, well understood

[@aeshwer]

UNDERSTOOD

[@shripandey4120]

Understood sir, thnak u soo much sir

[@bhushankorg5606]

Confident in solving LIS now

[@parshchoradia9909]

Understood Sir!

[@vasanthgk02]

Everything looks fine! What I am wondering is how I can get this intuition on the go?

[@AdityaKumar-be7hx]

understood!

[@KiranKumar-sb3ti]

understood bro