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

Find maximum sum rectangle in 2D matrix.
/ tusharroy25
github.com/mis...
github.com/mis...

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

[@30saransh]

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

[@lakshaythegupta]

@@30saransh 💯🤣

[@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 !!

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

[@Cryogenics12]

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

[@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!

[@nitin7829]

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

[@saifurrahmanbhuiyan925]

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

[@KrishanaKantPareek]

***** No.

[@VishalSharma-hq5ti]

yes, its 4

[@dumbskull5593]

Yea, I'm pretty sure the max sum's supposed to be 4. He might have just made a typo.

[@SnapSHORT1]

ignore it

[@Felix-wo7qz]

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

[@nicolaswolyniec1354]

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

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

[@rajendrab6509]

Became Fan boy of Tushar Roy.. Great Explanation.

[@RaviKumar-vk6ib]

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

[@SmartProgramming]

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

[@rizz_z1380]

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

[@ashishgoyal2711]

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

[@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!

[@golamazamabbasy1565]

loud and clear,awesome

[@darshitdalal3273]

This is such a lovely and lucid explanation.

[@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!

[@abhimanyushekhawat2626]

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

[@deshabhaktg6530]

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

[@JAYLATHIA]

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

[@sanchitjain7204]

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

[@nayanjain5761]

Tushar Sir you are awesome.

[@pramichak6762]

The best algo teacher..

[@argc]

amazing algorithm and explanation/video. thanks!

[@abdullahalnayem1849]

Thanks brother. You really made coding simple.

[@niranjanagrawal294]

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

[@saifurrahmanbhuiyan925]

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

[@harshpanwar1550]

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

[@vivekpatel8109]

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

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

[@hennessytj24]

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

[@user-bv6bi2sz8r]

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

[@beinghumanbeing5182]

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

[@petrugurita9728]

Very well explained . Hats off.

[@bhaskarsuthar7600]

Very nice explanation Tushar. Thanks for sharing.

[@harshsahu7825]

You really made coding easy. Thanks!!

[@muskangupta5873]

Amazing explanation sir

Great explanation, Thank You.

[@omkarpanhalkar6837]

thank you Tushar... You are the best

[@rituagrawal2218]

As usual; awesome explaination . Thanks Tushar

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

[@KirubaEbenezer]

@2:35 I can't understand how the current sum = 5....

[@khaledismail]

the current sum is 4 not 5

[@imrajya]

He made a small mistake. He has corrected the mistake by putting a caption "Sum is 4 not 5".(This mistake is repeated at 1 more place and corrected by putting the caption). Otherwise the solution and explanation are great.

[@mu3076]

He made a mistake,, it is 4

[@himanshu222222]

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

[@banaaboy6504]

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

[@JaySolanki91]

This is a really awesome 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.

[@akashmishra5630]

Respect for such nice efforts..

[@vicky501513]

Thanku Sir.. Amazing explanation..

[@AlokGuptakumar]

ignore two errors...video is awesome

[@Hameddelavar99]

I appreciate about this understandable video

[@clyt9636]

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

[@shyampatil8399]

This is a great help Tushar. Thanks a lot!

[@saumya1857]

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

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

[@abhishekjaiswal6492]

straightforward solution

[@darkprince2703]

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

[@dyrpa546]

I don't know why the time cost of creating a temporary array for sums of rows is "row". For creating it , we should get sum for each row, it will cost [Right - Left](get sum of a row)*Row(how many row we have). In this way , it's seems unreasonable that the time cost is only "row". I'm very confusing , who can tell me why?

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

[@shilinwang2958]

NICE explanation

[@bogdanrizescu8271]

Well done, Tushar! :D

[@srikanthvelpuri2973]

Good Explanation

[@sadmanahmmed2214]

your all vdos r awesome

[@aseemchakrabarthy9455]

Really helpful !! Nice explanation ...Thankyou

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

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

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

[@saifurrahmanbhuiyan925]

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

[@kuralamuthankathirvelan]

Tushar roy fans hit like !❤

[@Komachka92]

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

[@TheParvMudgil]

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

[@jonathanhoyos8191]

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

[@ErfanHossainShoaib]

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

[@apoorvchaturvedi6614]

Another nice explanation....:)

[@shekhataul5736]

Awesome tutorial, very thanks.

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

[@vin0summers]

Amazing description!

[@algorithmimplementer415]

You are a genius!!

[@durgeshdeep2544]

Thanks Tushar !!

[@sidhantkushwaha2766]

Excellent 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

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

[@SonuSonu-tk5pk]

zabardast samjhate hai aap sir ji

[@SergeyAngelov]

Great explanation!

[@rajatsran5213]

thanks bro nice explanation

[@HimanshukhantwalDeveloper]

easy explanation.. thanks for the help..

[@pleasantdayNwisdom]

4:15 Why not Max down as 3 since maximum subsequence sum so 3 6 0 0 total 9

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

[@jamesqiu6715]

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

[@JoanFFF]

bro you are so good

[@nihalsrivastava]

Awesome.

[@bruce160280]

Nice explanation man

[@517-geethaannapareddy8]

Clearly explained

[@afsarabc]

EExcellent Explanation.Thanks

[@carmenelenabruma4977]

I need to know how to adjust the values of maxUp and maxDown in C++ code. 🤔💻 Thank you!

[@rishuinindia]

That was perfect !

[@TheParvMudgil]

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