Maximum sum submatrix in sorted matrix

#1

I have the following questions :

  1. What is the need of the suffix sum matrix when we already have the idea to make the prefix sum matrix?
    2.As the mentor says that we need to find the suffix sum matrix, then find the highest sum. This all we could have also done with the help of a prefix sum matrix. In the both the method we need the brute force method to find the highest sum. What makes the use of suffix sum array unique?
  2. Can you also please share the program to prepare the suffix and prefix sum matrix which takes less time to execute?
  3. Also please share the code of the exiating problem of finding the maximum sum sub matrix.
#2

@Tiwary725 hey,we are using suffix sum matrix as the given matrix is row wise and column wise sorted ,as we have to calculate maximum sum submatrix so it will constitute of bottom right so in order to take bottom right element we have to start from bottom right thats why we have taken suffix matrix which will start from bottom right whereas in prefix matrix we were starting from top left therefore in this case we take suffix matrix.Now in order to calculate prefix matrix take another 2 d matrix and initialise bottim right element as bottom right element of suffix matrix and now start from second last row and column and current suffix element will be previous suffix element+ current matrix element.In this way suffix matrix will be calculated for prefix matrix start from top left element and apply same logic ,try to write its code yourself ,if you don’t get it than I will provide you.Happy coding :slight_smile:

#3

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.