# Maximum Difference

Posted: 27 Nov, 2020

Difficulty: Moderate

#### Given an n x n matrix mat[n][n] of integers, find the maximum value of mat[c][d] – mat[a][b] over all choices of indexes such that both c > a and d > b.

#### Example:-

```
1 2 3 4
5 6 7 8
1 9 2 3
In this example, the maximum value is 8 (mat[2][1]-mat[0][0]).
```

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

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

- Recursively find the answer of submatrix with top-left corner (i+1, j+1).

- Run a nested for loop from 0 to N-1 (Let’s say the iterator be j).
- Print the answer found.

Approach 2

** **Recursively call the function and memorize the maximum number of a submatrix in the top-left corner of the submatrix. Thus, DP[i][j] will contain the maximum number in the submatrix MAT[k][l] where i<=k<n and j<=l<n.

**Algorithm:-**

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

- Update answer as maximum of answer and DP[i+1][j+1]- MAT[i][j].

- Recursively find the answer of submatrix with top-left corner (i+1, j+1).

- Run a nested for loop from 0 to N-1 (Let’s say the iterator be j).
- Print the answer found.

Approach 3

Store the maximum number of a submatrix in the top-left corner of the submatrix. Thus, DP[i][j] will contain the maximum number in the submatrix MAT[k][l] where i<=k<n and j<=l<n.

**Algorithm:-**

- Initialize an empty matrix DP of size N*N and an empty variable to answer with -1.
- Run a for loop from N-1 to 0.
- Run a nested for loop from N-1 to 0.
- To calculate DP[i][j] update DP[i][j] as maximum of DP[i+1][j], DP[i][j+1], and MAT[i][j].

- Run a nested for loop from N-1 to 0.
- After the matrix DP is calculated, run a for loop from 0 to N-1.
- Run a nested for loop from 0 to N-1.
- Update answer as maximum of answer and DP[i+1][j+1] - MAT[i][j].

- Run a nested for loop from 0 to N-1.

3. Return ‘ANSWER’.

SIMILAR PROBLEMS

# Ninja And The Clan

Posted: 17 Apr, 2022

Difficulty: Moderate

# Prime Digit Sum

Posted: 17 Apr, 2022

Difficulty: Hard

# Rotate Clockwise

Posted: 19 Apr, 2022

Difficulty: Easy

# Count Numbers Containing Given Digit K Times

Posted: 20 Apr, 2022

Difficulty: Moderate

# Count Numbers With Equal First and Last Digit

Posted: 20 Apr, 2022

Difficulty: Moderate