# Max Submatrix

Posted: 4 Mar, 2021

Difficulty: Moderate

#### 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 :

- 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’)*

- We declare a variable

- Finally, we return
*‘MAX_SUM’*.

Approach 2

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’*.

- We run a loop for

- We declare an array/list
- 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’*.