Update appNew update is available. Click here to update.

Maximum Difference

Last Updated: 27 Nov, 2020
Difficulty: Moderate


Try Problem

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.


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