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

Find maximum sum rectangle in 2D matrix.

[khaleja]

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

[Official-tknc]

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

[youngmoney]

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.

[ranavij]

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

[Cryogenics]

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~~

[nitin]

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

[saifurrahmanbhuiyan]

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

[SmartProgramming]

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

[rajendrab]

Became Fan boy of Tushar Roy.. Great Explanation.

[harishkumarrayasam]

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

[RaviKumar-vkib]

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

[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

[mayur_madhwani]

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

[akshayjagtap]

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.

[nicolaswolyniec]

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

[Felix-woqz]

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

[darshitdalal]

This is such a lovely and lucid explanation.

[rizz_z]

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

[abhimanyushekhawat]

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