Last Updated: 4 Mar, 2021

Max Submatrix

Moderate

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 Approach

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 :

We declare a variable ‘MAX_SUM’ in which we store the maximum sum over all submatrices in the matrix.
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’)
Finally, we return ‘MAX_SUM’.

Solve now

02 Approach

As we know, we have to find the maximum sum submatrix. So, the idea is; first, we fix the left and right columns of the ‘MAT’. Then try to find the sum of elements of the submatrix from the left column to the right column for each row and store these values in a ‘MAX_SUM_VALUES’ array/list. After this, we apply Kadane’s algorithm on this array/list ‘MAX_SUM_VALUES’.

Here is the algorithm :

We declare a variable ‘MAX_SUM’ in which we store the maximum sum over all submatrices in the matrix.
We run a loop for ‘i’ = 0 to ‘M’:
- We declare an array/list ‘MAX_SUM_VALUES’ in which we store the sum of elements of the submatrix from the left column to the right column for each row
- We run a loop for ‘j’ = ‘i’ to ‘M’:
  - We run a loop for ‘k’ = 0 to ‘N’:
    - ‘MAX_SUM_VALUES[k]’ += ‘MAT[k][j]’
  - Apply kadane’s algorithm on this array/vector ‘MAX_SUM_VALUES’ and if the output is greater than ‘MAX_SUM’ then we update the value of ‘MAX_SUM’.
Finally, we return ‘MAX_SUM’.

Kadane’s algorithm:

We declare two variables ‘MAX_SO_FAR’ and ‘MAX_ENDING_HERE’ in which we store the maximum sum of contiguous subarray and maximum sum of contiguous subarray if we include the current element.
Initialize ‘MAX_SO_FAR’ and ‘MAX_ENDING_HERE’ with ‘MAX_SUM_VALUES[0].
We run a loop for ‘i’ = 1 to ‘N’:
- ‘MAX_ENDING_HERE’ = max(‘MAX_ENDING_HERE’ + ‘MAX_SUM_VALUES[i]’ , ‘MAX_SUM_VALUES[i]’)
- ‘MAX_SO_FAR’ = max(‘MAX_SO_FAR’, ‘MAX_ENDING_HERE’)
Finally, return ‘MAX_SO_FAR’.

Solve now