Maximum Sum Increasing Subsequence | Dynamic Programming | MSIS | LIS

[@shriyajaswani3400]

Thankuh🤠🥺 Understanding these hard problems to a level that you can make others understand it. then thinking out of the best way to explain it and also providing it for free. 🥺

[@techdose4u]

☺️

[@space_ace7710]

Best explanation I found!

[@techdose4u]

thanks :)

[@ashishranjan4623]

You should also have gone for NlogN approach. But whatever was there, it was well explained.

[@techdose4u]

Actually my intention for taking this question was to explain it as a variation of LIS.

[@ganeshkasar4340]

Can you share how this can be solved in NlogN. Because I am not sure if "NlogN approach of LIS" will work here or not

[@ashishranjan4623]

@@ganeshkasar4340 Suppose array is [3,1,4,2] Not we take an array [0,0,0,0,0]. 1. (3) so look at highest value before index 3. we have 0. update [0,0,0,3,0] 2. (1) highest value before index 1 is 0. Update [0,1,0,3,0] 3. (4) highest value before index 4 is 3. Update [0,1,0,3,7] 4. (2) highest value before 2 is 1. Update [0,1,3,3,7] Ho highest value is 7. This is n^2. But u can easily use segment tree to make "search for highest before" a logN operation. What if max in array is too high ? Then just use hash map to do coordinate compression and proceed in same way.

[@ganeshkasar4340]

Thanks a lot

[@RahulKumar-wf9xx]

Sir can you please make a video of Maximum product subarray problem as i feel it to be quite confusing and btw i follow your channel regularly !!

[@techdose4u]

I will see it. There are many problems pending :)

[@RahulKumar-wf9xx]

@@techdose4u Ok Thankyou sir and waiting for new dp problems !!

[@suvamroy6205]

@TECH DOSE Yes I need it too!! I am long following up for this problem. Please make video on it.

[@sanjeetsingh4743]

Hi thanks for the LIS videos, can you also make the N log N version of LIS ?

[@swaroopkv4540]

where we are checking if subsequence are in increasing order we r checking only element at i is greater than element at j

[@impatientgaming9868]

good one

[@shanmukhchandrayama8508]

is there any solution of o(nlogn) timecomplexity similar to that of lcs in nlogn

[@shubham-0152]

Sir pls upload videos on c++ stl like comparators, vector, pair, list, set or oops concept

[@E__ShameemahamedS-bx2ed]

i=0 prev=min element in array-1 int msis (arr [],i,prev) { if (i==n) return 0 if (prev>arr [i]) // exclusion case return msis (arr [],i+1,prev) else // max of include or exclude return max (msis (arr [],i+1,prev),arr [i]+msis (arr [],i+1,arr [i]) } I tried myself before seeing Ur solution Pls reply will this work?

[@E__ShameemahamedS-bx2ed]

Pls reply sir😢

[@barunsarraf8863]

I have one approach

[@techdose4u]

Your approach is LIS :)

[@barunsarraf8863]

@@techdose4u Yes. that is what i can relate to and solved with the same approach taking time n^2

[@barunsarraf8863]

can you help in solving minimum number of jumps to reach end problems, i often face problem in that and forget what approch was used there most of the time

[@E__ShameemahamedS-bx2ed]

Pls reply to my code

[@E__ShameemahamedS-bx2ed]

Pls reply to my code