Max sum submatrix sum

#1

can u explain the n^4 approaches for this problems?

#2

Hey,
Let’s see how submatrices are made
you fix top left corner and bottom right corner
So for each combination of top left corner and bottom right corner, one submatrix exists
for sum of any submatrix you’ll have to iterate over it
so selecting pairs of top left and bottom right corners takes n^2, for iterating over each submatrix takes n ^2 too, so it’s n^4.

Refer to this article for more detailed explanation: https://www.techiedelight.com/find-maximum-sum-submatrix-present-given-matrix/

#3

@mahimahans here we need to generate all the sub-matrix and in that we can store the current and maximum sum so far we have achieve means we have to generate all the possiblen^4 top left and bottom right. For that if fixed one top left and generate all bottom right it take 0(n^4) means two loop for generate the top left and two for bottom right and if we found the one sub-maxtrx we have to iterate over that again we required two more loop itself so , overall becomes the 6 loops n^6 how it is n^4 i didn’t get u

#4

Sorry, yeah that was O(n^6) approach

Here’s the optimized approach:-
Kadane’s algorithm for 1D array can be used to reduce the time complexity to O(n^3). The idea is to fix the left and right columns one by one and find the maximum sum contiguous rows for every left and right column pair. We basically find top and bottom row numbers (which have maximum sum) for every fixed left and right column pair. To find the top and bottom row numbers, calculate sun of elements in every row from left to right and store these sums in an array say temp[]. So temp[i] indicates sum of elements from left to right in row i. If we apply Kadane’s 1D algorithm on temp[], and get the maximum sum subarray of temp, this maximum sum would be the maximum possible sum with left and right as boundary columns. To get the overall maximum sum, we compare this sum with the maximum sum so far.

You can go through the following video tutorial if yo can’t understand
https://www.youtube.com/watch?v=yCQN096CwWM check this out.

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.