Maximum Difference

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
8 upvotes
Asked in companies
MicrosoftExpedia GroupHike

Problem statement

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]).
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
4
9 9 5 1 
4 5 8 0 
7 0 9 7 
5 5 5 6
2
1 2 
1 2
Sample Output 1 :
6
1
Explanation of Sample Output 1 :
In the first test case :

Choose a=3, b=2, c=4, and d=4. So we get 6 
(mat[4][4] - mat[3][2]) as the maximum value. So output will be 6.

 In the second test :

Choose a=1, b=1, c=2, and d=2. So we get 1 
(mat[4][4] - mat[3][2]) as the maximum value. So output will be 1.
Sample Input 2 :
2
4
1 2 3 4 
5 6 7 8
1 2 3 4 
1 2 3 4
1
1
Sample Output 2 :
7
0
Hint

Recursively find the maximum number of the submatrix.

Approaches (3)
Brute Force

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].
  2. Print the answer found.
Time Complexity

O(N^2*2^(N^2)), where ‘N’ is the size of the matrix.


 

We are finding the maximum number in the submatrix for every element in the matrix which takes O(2^(N*N)) time as we are finding the maximum of 2 smaller sub-matrixes at every step. Since the matrix itself contains N*N elements, the total Time complexity is O(N^2*2^(N*N)) where ‘N’ is the size of the matrix. 


 

Space Complexity

O(N*N), where ‘N’ is the size of the matrix.


 

The size of the recursion stack will be N*N hence the space complexity will be O(N^2).

Code Solution
(100% EXP penalty)
Maximum Difference
Full screen
Console