Find maximum sum rectangle in 2D matrix. / tusharroy25 github.com/mis... github.com/mis...
Пікірлер: 248
@khaleja267 жыл бұрын
2, 0, 2, -3 maximum sum using Kadence algorithm is 4
@anderson1018664 жыл бұрын
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.
@lakshyaagarwal20054 жыл бұрын
Yes it is 4
@biswamohandwari7803 жыл бұрын
to err is human
@30saransh2 жыл бұрын
Pain And Suffering, replayed that section 10 times to see how TF it's 5.
@lakshaythegupta2 жыл бұрын
@@30saransh 💯🤣
@Official-tk3nc4 жыл бұрын
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
@gauravchaudhari92794 жыл бұрын
True. Thank you and same to you. iiit-h student here
@maythecodesbewithyou294 жыл бұрын
all the best for future man
@ayushraj-zb6sv4 жыл бұрын
bit mesra here!
@rahulkumarchaubey42664 жыл бұрын
Nit jaipur here
@vikashkumarchaurasia12994 жыл бұрын
NIT jsr here !!
@youngmoney19909 жыл бұрын
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.
@Cryogenics128 жыл бұрын
Very well done video. Thank you for tracing steps and explaining logic without code. That's really important
@clusteringmiu5 жыл бұрын
omg it's 2019 and you are still contributing to the coding noobs like me! Love you~~
@rishabhratan29253 жыл бұрын
2021
@lolnoob50153 жыл бұрын
I'm from the future, 2026
@alanmarkkristensen28787 жыл бұрын
Beautiful! I was looking for a simple explanation, and this is by far the best i've found. Great work!
@nitin78293 ай бұрын
Coming back to this even after 6 years of college. Big Time Nostalgia !!!
@saifurrahmanbhuiyan9259 жыл бұрын
When, L = 0 and R = 0. isn't the max sum 4? Why is it 5?
@KrishanaKantPareek9 жыл бұрын
***** No.
@VishalSharma-hq5ti4 жыл бұрын
yes, its 4
@dumbskull55934 жыл бұрын
Yea, I'm pretty sure the max sum's supposed to be 4. He might have just made a typo.
@SnapSHORT13 жыл бұрын
ignore it
@Felix-wo7qz5 ай бұрын
Very good explanation, very clear. Thank you very much 👍🏻
@nicolaswolyniec13545 жыл бұрын
thanks! I was shocked at the first time for the current sum=5 instead 4, but the best explanation I found! :)
@mayur_madhwani032 жыл бұрын
What an explanation It was so clear that I wrote code on my own
@harishkumarrayasam9 жыл бұрын
Beautifully explained. Please upload more videos... Will recommend this channel to all my friends...
@rajendrab65099 жыл бұрын
Became Fan boy of Tushar Roy.. Great Explanation.
@RaviKumar-vk6ib4 жыл бұрын
Thanks tushar...you are doing a wonderful job and helping the coding community a lot...big follower of your videos
@SmartProgramming5 жыл бұрын
perfectly explained, thanks a lot for this tutorial 👍👍👍👍🙂🙂🙂🙂
@rizz_z13802 жыл бұрын
explanation was very clear and I understood the solution in one go. Thanks.
@ashishgoyal27119 жыл бұрын
sir its amazing.... keep doing it lyk this.... thank u so much for the video
@princejohn41522 жыл бұрын
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). 🙂🙂🙂
@jy58868 жыл бұрын
Definitely the best algo instructor!
@golamazamabbasy15659 жыл бұрын
loud and clear,awesome
@darshitdalal3273 Жыл бұрын
This is such a lovely and lucid explanation.
@ZhihongCheng9 жыл бұрын
Hi brother, I am your fan! Thanks for the video!
@anyu81098 жыл бұрын
+Zhihong Cheng Me too. He explains those algorithms so clear and easy to understand.
@sandeepvulluri88875 жыл бұрын
@@anyu8109 hahaha me tooo!
@abhimanyushekhawat26267 жыл бұрын
Yeah you explained it very well but a little intuitive walk through for the algorithm will be great!
@deshabhaktg65303 жыл бұрын
Thanks for making such a great video. You made problem look really simple,.
@JAYLATHIA7 жыл бұрын
Awesome explanation with traces and step-by-step process...
@sanchitjain72047 жыл бұрын
Couldn't be more easier than this. Great job mate !
@nayanjain57613 жыл бұрын
Tushar Sir you are awesome.
@pramichak67628 жыл бұрын
The best algo teacher..
@argc2 жыл бұрын
amazing algorithm and explanation/video. thanks!
@abdullahalnayem18494 жыл бұрын
Thanks brother. You really made coding simple.
@niranjanagrawal2948 жыл бұрын
Hats off to you bro, you made the dynamic programming so simple!! Loved all your videos .. thanks once again man :-)
@saifurrahmanbhuiyan9259 жыл бұрын
the best channel for dynamic programming Bro plz continue . We r benifitted. I need Bitmask dp Thanks
@harshpanwar15503 жыл бұрын
Thanks a ton sir... U made it extremely easy to understand!!!!!!!
@vivekpatel81098 жыл бұрын
you are just awesome tushar sir... very very nice explaination
@xxmajia9 жыл бұрын
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
@anyu81098 жыл бұрын
+陈满砚 Nice discussion.
@hennessytj248 жыл бұрын
Thanks for posting this video. I found it informative and easy to follow. Great job!
@user-bv6bi2sz8r8 жыл бұрын
Great video, it helps me a lot! The explanation is very thorough.
@beinghumanbeing51823 жыл бұрын
*I think this guy is working in amazon* . Its been five years we met
@petrugurita97288 жыл бұрын
Very well explained . Hats off.
@bhaskarsuthar76008 жыл бұрын
Very nice explanation Tushar. Thanks for sharing.
@harshsahu78254 жыл бұрын
You really made coding easy. Thanks!!
@muskangupta58733 жыл бұрын
Amazing explanation sir
2 жыл бұрын
Great explanation, Thank You.
@omkarpanhalkar68377 жыл бұрын
thank you Tushar... You are the best
@rituagrawal22188 жыл бұрын
As usual; awesome explaination . Thanks Tushar
@akshayjagtap5952 жыл бұрын
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.
@KirubaEbenezer8 жыл бұрын
@2:35 I can't understand how the current sum = 5....
@khaledismail8 жыл бұрын
the current sum is 4 not 5
@imrajya7 жыл бұрын
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.
@mu30765 жыл бұрын
He made a mistake,, it is 4
@himanshu2222229 жыл бұрын
thanks a lot sir,.......the explanation is perfect .... thank u .......
@banaaboy65043 жыл бұрын
Five Stars!!! Thanks from Russia! ))))
@JaySolanki915 жыл бұрын
This is a really awesome approach!
@studyaccount7942 жыл бұрын
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.
@akashmishra56309 жыл бұрын
Respect for such nice efforts..
@vicky5015139 жыл бұрын
Thanku Sir.. Amazing explanation..
@AlokGuptakumar6 жыл бұрын
ignore two errors...video is awesome
@Hameddelavar99 Жыл бұрын
I appreciate about this understandable video
@clyt96369 жыл бұрын
great explanation Tushar! But can you explain how you come up with the algorithm. The intuitions that guide you towards this approach.
@shyampatil83997 жыл бұрын
This is a great help Tushar. Thanks a lot!
@saumya18578 жыл бұрын
you made the dynamic programming so simple, thank you :)
@MOHDSALMAN-sj2zu8 жыл бұрын
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
@abhishekjaiswal64923 жыл бұрын
straightforward solution
@darkprince2703 Жыл бұрын
The video was really good but the answer for the first iteration curr_sum is 4
@dyrpa5466 жыл бұрын
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-nt9mm6 жыл бұрын
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
@shilinwang29583 жыл бұрын
NICE explanation
@bogdanrizescu82715 жыл бұрын
Well done, Tushar! :D
@srikanthvelpuri29732 жыл бұрын
Good Explanation
@sadmanahmmed22148 жыл бұрын
your all vdos r awesome
@aseemchakrabarthy94558 жыл бұрын
Really helpful !! Nice explanation ...Thankyou
@Lisa-kk6go6 жыл бұрын
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.
@TheDon6407 жыл бұрын
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..
@Sonakshi1117 жыл бұрын
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.
@iskariotas7 жыл бұрын
I think that you could just write another condition: "Increment R, if L + R
@true_human_0075 жыл бұрын
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.
@saifurrahmanbhuiyan9259 жыл бұрын
The dynamic programming which works with bitwise operation , is called bitmask dp
@kuralamuthankathirvelan5 жыл бұрын
Tushar roy fans hit like !❤
@Komachka928 жыл бұрын
It is so perfect explanation! Thank you very much!!
@TheParvMudgil4 жыл бұрын
How is 2 + 2 = 5 if its perfect? Refer - 02:28
@jonathanhoyos81919 жыл бұрын
Thanx a lot!!! I really appreciate you to do this
@ErfanHossainShoaib9 жыл бұрын
Please add a video for sub squire matrix max sum. Thanks for your best effort .......
@apoorvchaturvedi66149 жыл бұрын
Another nice explanation....:)
@shekhataul57364 жыл бұрын
Awesome tutorial, very thanks.
@Raj-ev8um8 жыл бұрын
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 ).
@vin0summers9 жыл бұрын
Amazing description!
@algorithmimplementer4154 жыл бұрын
You are a genius!!
@durgeshdeep25449 жыл бұрын
Thanks Tushar !!
@sidhantkushwaha27666 жыл бұрын
Excellent explanation.
@rajcodingworld77688 жыл бұрын
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
@yernartalgatuly42528 жыл бұрын
Thanks for explanation. I have a question. at 2:36. Why your currentSum is 5? It should be 4
@yernartalgatuly42528 жыл бұрын
+Tushar Roy Ok. It doesn't matter. But I undertood this algorithm by your video. Thanks
@SonuSonu-tk5pk7 жыл бұрын
zabardast samjhate hai aap sir ji
@SergeyAngelov5 жыл бұрын
Great explanation!
@rajatsran52134 жыл бұрын
thanks bro nice explanation
@HimanshukhantwalDeveloper8 жыл бұрын
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
@bhagwatkumarsingh28208 жыл бұрын
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.
@lucastian60273 жыл бұрын
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
@jamesqiu67157 жыл бұрын
Looks OK... even with minor errors... but what is the heart of this algorithm? What's the DP nature in this question?
@JoanFFF4 жыл бұрын
bro you are so good
@nihalsrivastava8 жыл бұрын
Awesome.
@bruce1602808 жыл бұрын
Nice explanation man
@517-geethaannapareddy8 Жыл бұрын
Clearly explained
@afsarabc7 жыл бұрын
EExcellent Explanation.Thanks
@carmenelenabruma4977 Жыл бұрын
I need to know how to adjust the values of maxUp and maxDown in C++ code. 🤔💻 Thank you!