Find the maximum value of M[c][d] – M[a][b] over all choices of indexes

Given a square matrix of integers, find the maximum value of M[c][d] – M[a][b] over all choices of indexes such that c > a and d > b in one traversal of the matrix.


 

For example,


Input Matrix:

{  1,  2, -1, -4, -20 }
{ -8, -3,  4,  2,   1 }
{  3,  8,  6,  1,   3 }
{ -4, -1,  1,  7,  -6 }
{  0, -4, 10, -5,   1 }

Output: The maximum value is 18 as M[4][2] – M[1][0] has maximum difference.

 
Naive solution would be to find M[c][d] for all values M[a][b] in the matrix, having the maximum value and satisfies c > a and d > b. We keep track of maximum value found so far in a variable and finally return the maximum value. The implementation can be seen here and runs in O(n^4) time which is very poor.

 
The efficient solution is to use an auxiliary matrix whose index (i, j) will store the value of the maximum element in the input matrix from the coordinates (i, j) to (N-1, N-1). We keep track of maximum value found so far in a variable and finally return the maximum value.

 

Download   Run Code

Output:

The Maximum Value is 18

 
Above solution uses extra space for auxillary matrix. We can avoid that by using the input matrix instead.

 
Author: Aditya Goel

 
Exercise: Extend the solution to print index (a, b) and (c, d).

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 






Leave a Reply

avatar
  Subscribe  
Notify of