Max Submatrix

Posted: 4 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

Ninja has been given a matrix ‘MAT’ of integers having size ‘N’ x ‘M’ i.e. N rows and M columns. Ninja has to find the maximum sum submatrix in it. In other words, he has to find the maximum sum over all submatrices in the matrix.

For example: For the ‘MAT’ given below, the maximum sum submatrix having a sum of 29 is highlighted in red.

Input Format :
The first line of input contains an integer ‘T’ denoting the number of test cases. Then each test case follows.

The first line of each test case contains two space-separated integers ‘N’ and ‘M’ representing the number of rows and columns respectively. size of the matrix ‘MAT’.

The next ‘N’ lines of each test case contain ‘M’ single space-separated integers denoting the values of ‘MAT’.
Output Format :
For each test case, print the maximum sum over all submatrices in ‘MAT’.

Print the output of each test case in a separate line.
Note :
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints :
1 <= ‘T’ <= 100
1 <= ‘N’, ‘M’<= 100
-100000 <= ‘MAT[i][j]’ <=100000

Where 'MAT[i][j]' represents the value at cell(i, j).

Time limit: 1 sec
Approach 1

The brute force approach is we check for every possible submatrix in the given ‘MAT’.

  • 4 nested loops are required to select every submatrix of the matrix.
  • 2 nested loops are required to take the sum of all the elements of the submatrix.

Here is the algorithm :

  1. We declare a variable ‘MAX_SUM’ in which we store the maximum sum over all submatrices in the matrix.
  2. We run a loop for ‘i’ = 0 to ‘N’:
    • We run a loop for ‘j’ = 0 to ‘M’:
      • We run a loop for ‘k’ = ‘i’ to ‘N’:
        • We run a loop for ‘l’ = ‘j’ to ‘M’:
          • We declare a variable ‘tmpSum’ in which we store the sum of the current submatrix
          • We run a loop for ‘q’ = ‘i’ to ‘k’:
            • We run a loop for ‘r’ = ‘j’ to ‘l’:
              • ‘tmpSum’ += mat[q][r]
          • ‘maxSum’ = max(‘maxSum’, ‘tmpSum’)
  3. Finally, we return ‘MAX_SUM’.
Try Problem