Max Submatrix

Moderate
0/80
Average time to solve is 20m
17 upvotes
Asked in companies
AmazonMeeshoFlipkart limited

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
1
4 4
-1 -2 -2 -2
-5 -4 -1 -9 
-3 -2 -6 -3
-4 -3 -3 -2
Sample Output 1 :
-1

Explanation Of Sample Output 1 :

For sample test case 1 : 


In this sample test case, the maximum sum submatrix in the matrix ‘MAT’ is at cell (0,0) with sum -1.
Sample Input 2 :
1
3 3
1 2 3
4 5 6
7 8 9
Sample Output 2 :
45

Explanation Of Sample Output 1 :

For sample test case 1 : 


In this sample test case, the maximum sum submatrix in the matrix ‘MAT’ is having cells (0,0), (0,2), (2,0), (2,2) with sum 45.
Hint

Think of the Brute Force Approach.

Approaches (2)
Brute Force

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’.
Time Complexity

O((N * M) ^ 3) Where ‘N’ and ‘M’ denote the number of rows and columns of the matrix ‘MAT’.

 

Because we are using 6 nested loops. 4 nested loops are required to select every submatrix of the matrix And 2 nested loops are required to take the sum of all the elements of the submatrix. Hence, the overall time complexity is O((N * M) ^ 3).

Space Complexity

O(1).

 

Because we are not using any extra space for finding our resultant answer.

Code Solution
(100% EXP penalty)
Max Submatrix
Full screen
Console