Maximum Sum Rectangular Submatrix in Matrix dynamic programming/2D kadane

[@khaleja26]

2, 0, 2, -3 maximum sum using Kadence algorithm is 4

[@anderson101866]

I believe it just a typo, so it should be 4. It might not be a big problem because it doesn't affect the final answer in this video.

[@lakshyaagarwal2005]

Yes it is 4

[@biswamohandwari780]

to err is human

[@butterChickenAndNaan98]

Pain And Suffering, replayed that section 10 times to see how TF it's 5.

[@lakshaythegupta]

@@butterChickenAndNaan98 💯🤣

[@Official-tk3nc]

if you are watching this in lockdown you are one of the rare species on the earth . many students are wasting their time on facebook, youtube, twitter, netflix, watching movies playing pubg, but you are working hard to achieve something . ALL the best ...nitj student here

[@gauravchaudhari9279]

True. Thank you and same to you. iiit-h student here

[@maythecodesbewithyou29]

all the best for future man

[@ayushraj-zb6sv]

bit mesra here!

[@rahulkumarchaubey4266]

Nit jaipur here

[@vikashkumarchaurasia1299]

NIT jsr here !!

[@nitin7829]

Coming back to this even after 6 years of college. Big Time Nostalgia !!!

[@Cryogenics12]

Very well done video. Thank you for tracing steps and explaining logic without code. That's really important

[@youngmoney1990]

Nice initiative dude. I'd advice you to give a proof of concept of the algorithm you are walking through, like why this would actually always work. For some algorithms its trivial but for some it's not. Its always good for the sake of completeness. Like in this example, for every column_start and column_end combination you are finding the maximum submatrix and then taking the max of all those combinations. Anyways, a really good initiative and keep up the good work.

[@clusteringmiu]

omg it's 2019 and you are still contributing to the coding noobs like me! Love you~~

[@rishabhratan2925]

2021

[@lolnoob5015]

I'm from the future, 2026

[@alanmarkkristensen2878]

Beautiful! I was looking for a simple explanation, and this is by far the best i've found. Great work!

[@rajendrab6509]

Became Fan boy of Tushar Roy.. Great Explanation.

[@mayur_madhwani03]

What an explanation It was so clear that I wrote code on my own

[@harishkumarrayasam]

Beautifully explained. Please upload more videos... Will recommend this channel to all my friends...

[@nicolaswolyniec1354]

thanks! I was shocked at the first time for the current sum=5 instead 4, but the best explanation I found! :)

[@darshitdalal3273]

This is such a lovely and lucid explanation.

[@RaviKumar-vk6ib]

Thanks tushar...you are doing a wonderful job and helping the coding community a lot...big follower of your videos

[@Felix-wo7qz]

Very good explanation, very clear. Thank you very much 👍🏻

[@rizz_z1380]

explanation was very clear and I understood the solution in one go. Thanks.

[@princejohn4152]

When understand same the algorithm from other source, then time complexity of understanding the algorithm is O(n^2). But listening your lecture on same algorith, then time complexity of understanding is reduce to O(n). 🙂🙂🙂

[@jy5886]

Definitely the best algo instructor!

[@deshabhaktg6530]

Thanks for making such a great video. You made problem look really simple,.

[@JAYLATHIA]

Awesome explanation with traces and step-by-step process...

[@abhimanyushekhawat2626]

Yeah you explained it very well but a little intuitive walk through for the algorithm will be great!

[@SmartProgramming]

perfectly explained, thanks a lot for this tutorial 👍👍👍👍🙂🙂🙂🙂

[@ZhihongCheng]

Hi brother, I am your fan! Thanks for the video!

[@anyu8109]

+Zhihong Cheng Me too. He explains those algorithms so clear and easy to understand.

[@sandeepvulluri8887]

@@anyu8109 hahaha me tooo!

[@abdullahalnayem1849]

Thanks brother. You really made coding simple.

[@xxmajia]

awesome explanation, but i think there is a bug in your implmentation {code} for(int i=0; i < arr.length; i++){ maxSoFar += arr[i]; if(maxSoFar < 0){ maxSoFar = 0; currentStart = i+1; } if(max < maxSoFar){ maxStart = currentStart; maxEnd = i; max = maxSoFar; } } {code} you should check if(max < maxSoFar) before if(maxSoFar < 0), just image if the whole array is negative. you will end up with 0 as the max sum which is incorrect

[@anyu8109]

+陈满砚 Nice discussion.

[@akshayjagtap595]

This is a good initiative. But I find your videos focused on going through the procedure rather than explaining how one should approach the problem.

[@saifurrahmanbhuiyan925]

the best channel for dynamic programming Bro plz continue . We r benifitted. I need Bitmask dp Thanks

[@vivekpatel8109]

you are just awesome tushar sir... very very nice explaination

[@AlokGuptakumar]

ignore two errors...video is awesome

[@pramichak6762]

The best algo teacher..

[@niranjanagrawal294]

Hats off to you bro, you made the dynamic programming so simple!! Loved all your videos .. thanks once again man :-)

[@ashishgoyal2711]

sir its amazing.... keep doing it lyk this.... thank u so much for the video

[@bhaskarsuthar7600]

Very nice explanation Tushar. Thanks for sharing.

[@darkprince2703]

The video was really good but the answer for the first iteration curr_sum is 4

[@harshpanwar1550]

Thanks a ton sir... U made it extremely easy to understand!!!!!!!

[@sanchitjain7204]

Couldn't be more easier than this. Great job mate !

[@petrugurita9728]

Very well explained . Hats off.

[@argc]

amazing algorithm and explanation/video. thanks!

[@beinghumanbeing5182]

*I think this guy is working in amazon* . Its been five years we met

[@rituagrawal2218]

As usual; awesome explaination . Thanks Tushar

[@harshsahu7825]

You really made coding easy. Thanks!!

[@nayanjain5761]

Tushar Sir you are awesome.

[@hennessytj24]

Thanks for posting this video. I found it informative and easy to follow. Great job!

[@程龙-b1w]

Great video, it helps me a lot! The explanation is very thorough.

[@MOHDSALMAN-sj2zu]

I found this link on geeksforgeeks, u explained this algorithm much better than geeks , it really helped me to understand what actually is going on. Will u plz make more videos of some difficult article which r on geeksforgeeks

[@bhagwatkumarsingh2820]

Hi Tushar , It was a great help from your tutorial . I understand the logic so cool that I was able to write the code in one go.

[@lucastian6027]

No one is doubting the time complexity? After you got the column sums stored at the buffer with size = row, you will need (row * row) time to find the maximum sum. So the time complexity should be col * col * row * row

[@golamazamabbasy1565]

loud and clear,awesome

[@akashmishra5630]

Respect for such nice efforts..

[@muskangupta5873]

Amazing explanation sir

[@jaikrishnan4249]

at 11.22 current sum is 8 not 7..small mistake..but the explanation was excellent....

[@saumya1857]

you made the dynamic programming so simple, thank you :)

[@JaySolanki91]

This is a really awesome approach!

[@clyt9636]

great explanation Tushar! But can you explain how you come up with the algorithm. The intuitions that guide you towards this approach.

[@studyaccount794]

Please tell the explanation why we are going to use dynamic programming. In some problems like lcs and others it's obvious that there was a recursion and we had to optimize that but this problem is different.

[@shubhamsingh-nt9mm]

we could'nt ask for more..excellent explaination ..thanks alot,we hope u upload videos on other topics..i know dp is ur fav :P

[@omkarpanhalkar6837]

thank you Tushar... You are the best

[@himanshu222222]

thanks a lot sir,.......the explanation is perfect .... thank u .......

[@sadmanahmmed2214]

your all vdos r awesome

[@saifurrahmanbhuiyan925]

The dynamic programming which works with bitwise operation , is called bitmask dp

[@SonuSonu-tk5pk]

zabardast samjhate hai aap sir ji

[@ErfanHossainShoaib]

Please add a video for sub squire matrix max sum. Thanks for your best effort .......

[@shyampatil8399]

This is a great help Tushar. Thanks a lot!

[@TheDon640]

Thankyou Sir you are doing fabulous job ...But don't you think we have to repeat same algo row by row also and then compare these two (colum vs row) which submatrix has maximum cost..Because i have done this with row operation and got max_cost=27..

[@Komachka92]

It is so perfect explanation! Thank you very much!!

[@TheParvMudgil]

How is 2 + 2 = 5 if its perfect? Refer - 02:28

[@Hameddelavar99]

I appreciate about this understandable video

[@sandeepmukherjee8927]

Nice initiative sir but pls upload the code in C++ also.

[@sonicabathija4464]

simply justt waaooo explanation......

[@banaaboy6504]

Five Stars!!! Thanks from Russia! ))))

[@Sonakshi111]

Hi Tushar. Can you post a video on " Max Sum of Rectangle No Larger Than K"? It's somewhat similar but has a different trick to calculate the sum in the end.

[@iskariotas]

I think that you could just write another condition: "Increment R, if L + R

[@true_human_007]

This solution does not work. You are restricting the use of all column by the solution. Most of the case, we will not reach to last column. We don't have to limit the sum of complete column to K. Complete sum of column is not required. Partial sum of column would be fine when satisfying our logic. This means our result rectangle may have side = length of input matrix.

[@aseemchakrabarthy9455]

Really helpful !! Nice explanation ...Thankyou

[@shekhataul5736]

Awesome tutorial, very thanks.

[@vicky501513]

Thanku Sir.. Amazing explanation..

[@yernartalgatuly4252]

Thanks for explanation. I have a question. at 2:36. Why your currentSum is 5? It should be 4

[@yernartalgatuly4252]

+Tushar Roy Ok. It doesn't matter. But I undertood this algorithm by your video. Thanks

[@sidhantkushwaha2766]

Excellent explanation.

[@shilinwang2958]

NICE explanation

[@abhishekjaiswal6492]

straightforward solution

[@deepTh00ught]

For the one who are confused cuz of 2+2=5 it is wrong, but doesn't change the answer and algorithm

[@jonathanhoyos8191]

Thanx a lot!!! I really appreciate you to do this

[@algorithmimplementer415]

You are a genius!!

[@Raj-ev8um]

thanks for the video Tushar...! if the size of sub-matrix is already given then what can be the best approach to solve this problem. ( i think naive approach will cost n^4 ).

[@zhenqiangsu2966]

The time complexity is col*col*row*row if include the Kadane algo? Like the brute force method?

[@vin0summers]

Amazing description!

[@meshmuhammad6927]

awesome man but it will be better to say lines of code or just a pseudo code while explaining , try this

[@srikanthvelpuri2973]

Good Explanation

[@bruce160280]

Nice explanation man

[@bogdanrizescu8271]

Well done, Tushar! :D

[@jagdishwarbiradar1763]

if go with rows like you are going with cols , can I get solution ?

[@minakshikudalkar557]

We want a collab!! Tushar Roy and Ben (Back to Back SWE)!! haha Great explanation Tushar thank you :)

[@jamesqiu6715]

Looks OK... even with minor errors... but what is the heart of this algorithm? What's the DP nature in this question?

[@USIndian51]

Wen, L = 0 and R = 0. isn't the max sum 4? Why is it 5?

[@USIndian51]

***** Sorry, I didn't see the bubble.Anyway, thanks for the clarification.

[@USIndian51]

***** By the way,is it possible for you to provide an explanation/solution for maximal palandrome using Suffix Trees? Thanks in advance.

[@raviraaja1282]

I have checked your code in github, what if all elements in matrix are negative (< 0) , kadanes algorithm will result in 0 but , there is another approach to resolve (using dynamic programming) in dp approach how to find array index start and end ?

[@freewind7894]

i watched a lot of your videos, good explanations. keep on bro``

[@Lisa-kk6go]

Why do we only apply kadane to cols instead of both cols and rows? It seems that we are only adding numbers when we move L and R.

[@HimanshukhantwalDeveloper]

easy explanation.. thanks for the help..

[@apoorvchaturvedi6614]

Another nice explanation....:)

[@rajcodingworld7768]

I understood the mechanics of it but not the intuition behind it.. how it's giving max values if we follow that process.. I appreciate if you can explain - Raj

[@SergeyAngelov]

Great explanation!

[@shreyanshsharma8761]

can it be done in better time complexity?

[@ولاءعلي-خ8ط]

شرح جميل. شكرا استفدت كتير

[@kuralamuthankathirvelan]

Tushar roy fans hit like !❤