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.

Output:

The Maximum Value is 18

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

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

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 🙂