# Maximum Difference

Posted: 27 Nov, 2020
Difficulty: Moderate

## PROBLEM STATEMENT

#### Example:-

``````1 2 3 4
5 6 7 8
1 9 2 3

In this example, the maximum value is 8 (mat-mat).
``````
##### Input format :
``````The first line contains a single integer T representing the number of test cases.

The first line of each test case contains a single integer ‘N’ denoting the size of the matrix.

The next N lines contain ‘N’ integers each where each line denotes a row of the matrix.
``````
##### Output Format :
``````For each test case, print an integer denoting the maximum value of mat[c][d] – mat[a][b].

The output of each test case should be printed in a separate line.
``````
##### Note:
``````You are not required to print anything, it has already been taken care of. Just implement the function.
``````
##### Constraints :
``````1 <= N <= 10^2
1 <= mat[i][j] <= 10^8

Time Limit - 1 sec
`````` Approach 1

Recursively call the function and find the maximum number of the submatrix and update the answer for every element of the matrix.

Algorithm:-

1. Run a for loop from 0 to N-1  (Let’s say the iterator be i).
1. Run a nested for loop from 0 to N-1 (Let’s say the iterator be j).
1. Recursively find the answer of submatrix with top-left corner (i+1, j+1).
1. If i+1== N or j+1== N return -infinity.
2. Update answer as maximum of answer and maximum value in the submatrix with top-left corner (i,j)- MAT[i][j].