Find a specific pair in Matrix

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:

```Input:
mat[N][N] = {{ 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: 18
The maximum value is 18 as mat[4][2]
- mat[1][0] = 18 has maximum difference. ```

The program should do only ONE traversal of the matrix. i.e. expected time complexity is O(n2)

A simple solution would be to apply Brute-Force. For all values mat(a, b) in the matrix, we find mat(c, d) that has maximum value such that c > a and d > b and keeps on updating maximum value found so far. We finally return the maximum value.

Below is its implementation.

C++

 `// A Naive method to find maximum value of mat[d][e] ` `// - ma[a][b] such that d > a and e > b ` `#include ` `using` `namespace` `std; ` `#define N 5 ` ` `  `// The function returns maximum value A(d,e) - A(a,b) ` `// over all choices of indexes such that both d > a ` `// and e > b. ` `int` `findMaxValue(``int` `mat[][N]) ` `{ ` `    ``// stores maximum value ` `    ``int` `maxValue = INT_MIN; ` ` `  `    ``// Consider all possible pairs mat[a][b] and ` `    ``// mat[d][e] ` `    ``for` `(``int` `a = 0; a < N - 1; a++) ` `    ``for` `(``int` `b = 0; b < N - 1; b++) ` `        ``for` `(``int` `d = a + 1; d < N; d++) ` `        ``for` `(``int` `e = b + 1; e < N; e++) ` `            ``if` `(maxValue < (mat[d][e] - mat[a][b])) ` `                ``maxValue = mat[d][e] - mat[a][b]; ` ` `  `    ``return` `maxValue; ` `} ` ` `  `// Driver program to test above function ` `int` `main() ` `{ ` `int` `mat[N][N] = { ` `                ``{ 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 } ` `            ``}; ` `    ``cout << ``"Maximum Value is "` `        ``<< findMaxValue(mat); ` ` `  `    ``return` `0; ` `} `

Java

 `// A Naive method to find maximum value of mat1[d][e] ` `// - ma[a][b] such that d > a and e > b ` `import` `java.io.*; ` `import` `java.util.*; ` `  `  `class` `GFG  ` `{ ` `    ``// The function returns maximum value A(d,e) - A(a,b) ` `    ``// over all choices of indexes such that both d > a ` `    ``// and e > b. ` `    ``static` `int` `findMaxValue(``int` `N,``int` `mat[][]) ` `    ``{ ` `        ``// stores maximum value ` `        ``int` `maxValue = Integer.MIN_VALUE; ` `      `  `        ``// Consider all possible pairs mat[a][b] and ` `        ``// mat1[d][e] ` `        ``for` `(``int` `a = ``0``; a < N - ``1``; a++) ` `          ``for` `(``int` `b = ``0``; b < N - ``1``; b++) ` `             ``for` `(``int` `d = a + ``1``; d < N; d++) ` `               ``for` `(``int` `e = b + ``1``; e < N; e++) ` `                  ``if` `(maxValue < (mat[d][e] - mat[a][b])) ` `                      ``maxValue = mat[d][e] - mat[a][b]; ` `      `  `        ``return` `maxValue; ` `    ``} ` `      `  `    ``// Driver code ` `    ``public` `static` `void` `main (String[] args)  ` `    ``{ ` `        ``int` `N = ``5``; ` ` `  `        ``int` `mat[][] = { ` `                      ``{ ``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` `} ` `                   ``}; ` ` `  `        ``System.out.print(``"Maximum Value is "` `+  ` `                         ``findMaxValue(N,mat)); ` `    ``} ` `} ` `  `  `// This code is contributed ` `// by Prakriti Gupta `

Python 3

 `# A Naive method to find maximum  ` `# value of mat[d][e] - mat[a][b] ` `# such that d > a and e > b ` `N ``=` `5` ` `  `# The function returns maximum  ` `# value A(d,e) - A(a,b) over  ` `# all choices of indexes such  ` `# that both d > a and e > b. ` `def` `findMaxValue(mat): ` `     `  `    ``# stores maximum value ` `    ``maxValue ``=` `0` ` `  `    ``# Consider all possible pairs  ` `    ``# mat[a][b] and mat[d][e] ` `    ``for` `a ``in` `range``(N ``-` `1``): ` `        ``for` `b ``in` `range``(N ``-` `1``): ` `            ``for` `d ``in` `range``(a ``+` `1``, N): ` `                ``for` `e ``in` `range``(b ``+` `1``, N): ` `                    ``if` `maxValue < ``int` `(mat[d][e] ``-`  `                                       ``mat[a][b]): ` `                        ``maxValue ``=` `int``(mat[d][e] ``-`  `                                       ``mat[a][b]); ` ` `  `    ``return` `maxValue; ` ` `  `# Driver Code ` `mat ``=` `[[ ``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` `]]; ` `        `  `print``(``"Maximum Value is "` `+`  `       ``str``(findMaxValue(mat))) ` `       `  `# This code is contributed  ` `# by ChitraNayal `

C#

 `// A Naive method to find maximum  ` `// value of mat[d][e] - mat[a][b] ` `// such that d > a and e > b ` `using` `System; ` `class` `GFG ` `{ ` `     `  `    ``// The function returns ` `    ``// maximum value A(d,e) - A(a,b) ` `    ``// over all choices of indexes  ` `    ``// such that both d > a ` `    ``// and e > b. ` `    ``static` `int` `findMaxValue(``int` `N,  ` `                            ``int` `[,]mat) ` `    ``{ ` `         `  `        ``//stores maximum value ` `        ``int` `maxValue = ``int``.MinValue; ` `     `  `        ``// Consider all possible pairs  ` `        ``// mat[a][b] and mat[d][e] ` `        ``for` `(``int` `a = 0; a< N - 1; a++) ` `        ``for` `(``int` `b = 0; b < N - 1; b++) ` `            ``for` `(``int` `d = a + 1; d < N; d++) ` `            ``for` `(``int` `e = b + 1; e < N; e++) ` `                ``if` `(maxValue < (mat[d, e] -  ` `                                ``mat[a, b])) ` `                    ``maxValue = mat[d, e] -  ` `                               ``mat[a, b]; ` ` `  `        ``return` `maxValue; ` `    ``} ` `     `  `    ``// Driver code ` `    ``public` `static` `void` `Main ()  ` `    ``{ ` `        ``int` `N = 5; ` ` `  `        ``int` `[,]mat = {{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}}; ` `        ``Console.Write(``"Maximum Value is "` `+  ` `                      ``findMaxValue(N,mat)); ` `    ``} ` `} ` ` `  `// This code is contributed  ` `// by ChitraNayal `

PHP

 ` \$a and \$e > \$b ` `\$N` `= 5; ` ` `  `// The function returns maximum  ` `// value A(d,e) - A(a,b) over  ` `// all choices of indexes such  ` `// that both \$d > \$a and \$e > \$b. ` `function` `findMaxValue(&``\$mat``) ` `{ ` `    ``global` `\$N``; ` `     `  `    ``// stores maximum value ` `    ``\$maxValue` `= PHP_INT_MIN; ` ` `  `    ``// Consider all possible  ` `    ``// pairs \$mat[\$a][\$b] and ` `    ``// \$mat[\$d][\$e] ` `    ``for` `(``\$a` `= 0; ``\$a` `< ``\$N` `- 1; ``\$a``++) ` `    ``for` `(``\$b` `= 0; ``\$b` `< ``\$N` `- 1; ``\$b``++) ` `        ``for` `(``\$d` `= ``\$a` `+ 1; ``\$d` `< ``\$N``; ``\$d``++) ` `        ``for` `(``\$e` `= ``\$b` `+ 1; ``\$e` `< ``\$N``; ``\$e``++) ` `            ``if` `(``\$maxValue` `< (``\$mat``[``\$d``][``\$e``] -  ` `                             ``\$mat``[``\$a``][``\$b``])) ` `                ``\$maxValue` `= ``\$mat``[``\$d``][``\$e``] -  ` `                            ``\$mat``[``\$a``][``\$b``]; ` ` `  `    ``return` `\$maxValue``; ` `} ` ` `  `// Driver Code ` `\$mat` `= ``array``(``array``(1, 2, -1, -4, -20), ` `             ``array``(-8, -3, 4, 2, 1), ` `             ``array``(3, 8, 6, 1, 3), ` `             ``array``(-4, -1, 1, 7, -6), ` `             ``array``(0, -4, 10, -5, 1)); ` `             `  `echo` `"Maximum Value is "` `.  ` `       ``findMaxValue(``\$mat``); ` ` `  `// This code is contributed  ` `// by ChitraNayal ` `?> `

Output:

`Maximum Value is 18`

The above program runs in O(n^4) time which is nowhere close to expected time complexity of O(n^2)

An efficient solution uses extra space. We pre-process the matrix such that index(i, j) stores max of elements in matrix from (i, j) to (N-1, N-1) and in the process keeps on updating maximum value found so far. We finally return the maximum value.

C++

 `// An efficient method to find maximum value of mat[d] ` `// - ma[a][b] such that c > a and d > b ` `#include ` `using` `namespace` `std; ` `#define N 5 ` ` `  `// The function returns maximum value A(c,d) - A(a,b) ` `// over all choices of indexes such that both c > a ` `// and d > b. ` `int` `findMaxValue(``int` `mat[][N]) ` `{ ` `    ``//stores maximum value ` `    ``int` `maxValue = INT_MIN; ` ` `  `    ``// maxArr[i][j] stores max of elements in matrix ` `    ``// from (i, j) to (N-1, N-1) ` `    ``int` `maxArr[N][N]; ` ` `  `    ``// last element of maxArr will be same's as of ` `    ``// the input matrix ` `    ``maxArr[N-1][N-1] = mat[N-1][N-1]; ` ` `  `    ``// preprocess last row ` `    ``int` `maxv = mat[N-1][N-1];  ``// Initialize max ` `    ``for` `(``int` `j = N - 2; j >= 0; j--) ` `    ``{ ` `        ``if` `(mat[N-1][j] > maxv) ` `            ``maxv = mat[N - 1][j]; ` `        ``maxArr[N-1][j] = maxv; ` `    ``} ` ` `  `    ``// preprocess last column ` `    ``maxv = mat[N - 1][N - 1];  ``// Initialize max ` `    ``for` `(``int` `i = N - 2; i >= 0; i--) ` `    ``{ ` `        ``if` `(mat[i][N - 1] > maxv) ` `            ``maxv = mat[i][N - 1]; ` `        ``maxArr[i][N - 1] = maxv; ` `    ``} ` ` `  `    ``// preprocess rest of the matrix from bottom ` `    ``for` `(``int` `i = N-2; i >= 0; i--) ` `    ``{ ` `        ``for` `(``int` `j = N-2; j >= 0; j--) ` `        ``{ ` `            ``// Update maxValue ` `            ``if` `(maxArr[i+1][j+1] - mat[i][j] > ` `                                            ``maxValue) ` `                ``maxValue = maxArr[i + 1][j + 1] - mat[i][j]; ` ` `  `            ``// set maxArr (i, j) ` `            ``maxArr[i][j] = max(mat[i][j], ` `                               ``max(maxArr[i][j + 1], ` `                                   ``maxArr[i + 1][j]) ); ` `        ``} ` `    ``} ` ` `  `    ``return` `maxValue; ` `} ` ` `  `// Driver program to test above function ` `int` `main() ` `{ ` `    ``int` `mat[N][N] = { ` `                      ``{ 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 } ` `                    ``}; ` `    ``cout << ``"Maximum Value is "`  `         ``<< findMaxValue(mat); ` ` `  `    ``return` `0; ` `} `

Java

 `// An efficient method to find maximum value of mat1[d] ` `// - ma[a][b] such that c > a and d > b ` `import` `java.io.*; ` `import` `java.util.*; ` `  `  `class` `GFG  ` `{ ` `    ``// The function returns maximum value A(c,d) - A(a,b) ` `    ``// over all choices of indexes such that both c > a ` `    ``// and d > b. ` `    ``static` `int` `findMaxValue(``int` `N,``int` `mat[][]) ` `    ``{ ` `        ``//stores maximum value ` `        ``int` `maxValue = Integer.MIN_VALUE; ` `      `  `        ``// maxArr[i][j] stores max of elements in matrix ` `        ``// from (i, j) to (N-1, N-1) ` `        ``int` `maxArr[][] = ``new` `int``[N][N]; ` `      `  `        ``// last element of maxArr will be same's as of ` `        ``// the input matrix ` `        ``maxArr[N-``1``][N-``1``] = mat[N-``1``][N-``1``]; ` `      `  `        ``// preprocess last row ` `        ``int` `maxv = mat[N-``1``][N-``1``];  ``// Initialize max ` `        ``for` `(``int` `j = N - ``2``; j >= ``0``; j--) ` `        ``{ ` `            ``if` `(mat[N-``1``][j] > maxv) ` `                ``maxv = mat[N - ``1``][j]; ` `            ``maxArr[N-``1``][j] = maxv; ` `        ``} ` `      `  `        ``// preprocess last column ` `        ``maxv = mat[N - ``1``][N - ``1``];  ``// Initialize max ` `        ``for` `(``int` `i = N - ``2``; i >= ``0``; i--) ` `        ``{ ` `            ``if` `(mat[i][N - ``1``] > maxv) ` `                ``maxv = mat[i][N - ``1``]; ` `            ``maxArr[i][N - ``1``] = maxv; ` `        ``} ` `      `  `        ``// preprocess rest of the matrix from bottom ` `        ``for` `(``int` `i = N-``2``; i >= ``0``; i--) ` `        ``{ ` `            ``for` `(``int` `j = N-``2``; j >= ``0``; j--) ` `            ``{ ` `                ``// Update maxValue ` `                ``if` `(maxArr[i+``1``][j+``1``] - mat[i][j] > maxValue) ` `                    ``maxValue = maxArr[i + ``1``][j + ``1``] - mat[i][j]; ` `      `  `                ``// set maxArr (i, j) ` `                ``maxArr[i][j] = Math.max(mat[i][j], ` `                                   ``Math.max(maxArr[i][j + ``1``], ` `                                       ``maxArr[i + ``1``][j]) ); ` `            ``} ` `        ``} ` `      `  `        ``return` `maxValue; ` `    ``} ` `     `  `    ``// Driver code ` `    ``public` `static` `void` `main (String[] args)  ` `    ``{ ` `        ``int` `N = ``5``; ` ` `  `        ``int` `mat[][] = { ` `                      ``{ ``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` `} ` `                   ``}; ` ` `  `        ``System.out.print(``"Maximum Value is "` `+  ` `                           ``findMaxValue(N,mat)); ` `    ``} ` `} ` `  `  `// Contributed by Prakriti Gupta `

Python3

 `# An efficient method to find maximum value  ` `# of mat[d] - ma[a][b] such that c > a and d > b ` ` `  `import` `sys ` `N ``=` `5` ` `  `# The function returns maximum value  ` `# A(c,d) - A(a,b) over all choices of  ` `# indexes such that both c > a and d > b. ` `def` `findMaxValue(mat): ` ` `  `    ``# stores maximum value ` `    ``maxValue ``=` `-``sys.maxsize ``-``1` ` `  `    ``# maxArr[i][j] stores max of elements  ` `    ``# in matrix from (i, j) to (N-1, N-1) ` `    ``maxArr ``=` `[[``0` `for` `x ``in` `range``(N)] ` `                 ``for` `y ``in` `range``(N)] ` ` `  `    ``# last element of maxArr will be  ` `    ``# same's as of the input matrix ` `    ``maxArr[N ``-` `1``][N ``-` `1``] ``=` `mat[N ``-` `1``][N ``-` `1``] ` ` `  `    ``# preprocess last row ` `    ``maxv ``=` `mat[N ``-` `1``][N ``-` `1``]; ``# Initialize max ` `    ``for` `j ``in` `range` `(N ``-` `2``, ``-``1``, ``-``1``): ` `     `  `        ``if` `(mat[N ``-` `1``][j] > maxv): ` `            ``maxv ``=` `mat[N ``-` `1``][j] ` `        ``maxArr[N ``-` `1``][j] ``=` `maxv ` `     `  `    ``# preprocess last column ` `    ``maxv ``=` `mat[N ``-` `1``][N ``-` `1``] ``# Initialize max ` `    ``for` `i ``in` `range` `(N ``-` `2``, ``-``1``, ``-``1``): ` `     `  `        ``if` `(mat[i][N ``-` `1``] > maxv): ` `            ``maxv ``=` `mat[i][N ``-` `1``] ` `        ``maxArr[i][N ``-` `1``] ``=` `maxv ` ` `  `    ``# preprocess rest of the matrix ` `    ``# from bottom ` `    ``for` `i ``in` `range` `(N ``-` `2``, ``-``1``, ``-``1``): ` `     `  `        ``for` `j ``in` `range` `(N ``-` `2``, ``-``1``, ``-``1``): ` `         `  `            ``# Update maxValue ` `            ``if` `(maxArr[i ``+` `1``][j ``+` `1``] ``-` `                ``mat[i][j] > maxValue): ` `                ``maxValue ``=` `(maxArr[i ``+` `1``][j ``+` `1``] ``-`  `                                       ``mat[i][j]) ` ` `  `            ``# set maxArr (i, j) ` `            ``maxArr[i][j] ``=` `max``(mat[i][j],  ` `                           ``max``(maxArr[i][j ``+` `1``],  ` `                               ``maxArr[i ``+` `1``][j])) ` `         `  `    ``return` `maxValue ` ` `  `# Driver Code ` `mat ``=` `[[ ``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` `]] ` `                     `  `print` `(``"Maximum Value is"``, ` `        ``findMaxValue(mat)) ` ` `  `# This code is contributed by iAyushRaj `

C#

 `// An efficient method to find  ` `// maximum value of mat1[d] ` `// - ma[a][b] such that c > a  ` `// and d > b ` `using` `System; ` `class` `GFG  { ` `     `  `    ``// The function returns ` `    ``// maximum value A(c,d) - A(a,b) ` `    ``// over all choices of indexes  ` `    ``// such that both c > a ` `    ``// and d > b. ` `    ``static` `int` `findMaxValue(``int` `N, ``int` `[,]mat) ` `    ``{ ` `         `  `        ``//stores maximum value ` `        ``int` `maxValue = ``int``.MinValue; ` `     `  `        ``// maxArr[i][j] stores max  ` `        ``// of elements in matrix ` `        ``// from (i, j) to (N-1, N-1) ` `        ``int` `[,]maxArr = ``new` `int``[N, N]; ` `     `  `        ``// last element of maxArr  ` `        ``// will be same's as of ` `        ``// the input matrix ` `        ``maxArr[N - 1, N - 1] = mat[N - 1,N - 1]; ` `     `  `        ``// preprocess last row ` `         ``// Initialize max ` `        ``int` `maxv = mat[N - 1, N - 1]; ` `        ``for` `(``int` `j = N - 2; j >= 0; j--) ` `        ``{ ` `            ``if` `(mat[N - 1, j] > maxv) ` `                ``maxv = mat[N - 1, j]; ` `            ``maxArr[N - 1, j] = maxv; ` `        ``} ` `     `  `        ``// preprocess last column ` `        ``// Initialize max ` `        ``maxv = mat[N - 1,N - 1];  ` `        ``for` `(``int` `i = N - 2; i >= 0; i--) ` `        ``{ ` `            ``if` `(mat[i, N - 1] > maxv) ` `                ``maxv = mat[i,N - 1]; ` `            ``maxArr[i,N - 1] = maxv; ` `        ``} ` `     `  `        ``// preprocess rest of the ` `        ``// matrix from bottom ` `        ``for` `(``int` `i = N - 2; i >= 0; i--) ` `        ``{ ` `            ``for` `(``int` `j = N - 2; j >= 0; j--) ` `            ``{ ` `                 `  `                ``// Update maxValue ` `                ``if` `(maxArr[i + 1,j + 1] -  ` `                     ``mat[i, j] > maxValue) ` `                    ``maxValue = maxArr[i + 1,j + 1] -  ` `                                         ``mat[i, j]; ` `     `  `                ``// set maxArr (i, j) ` `                ``maxArr[i,j] = Math.Max(mat[i, j], ` `                              ``Math.Max(maxArr[i, j + 1], ` `                              ``maxArr[i + 1, j]) ); ` `            ``} ` `        ``} ` `     `  `        ``return` `maxValue; ` `    ``} ` `     `  `    ``// Driver code ` `    ``public` `static` `void` `Main ()  ` `    ``{ ` `        ``int` `N = 5; ` ` `  `        ``int` `[,]mat = {{ 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 }}; ` `        ``Console.Write(``"Maximum Value is "` `+  ` `                        ``findMaxValue(N,mat)); ` `    ``} ` `} ` ` `  `// This code is contributed by nitin mittal. `

PHP

 ` a and d > b ` `\$N` `= 5; ` ` `  `// The function returns maximum  ` `// value A(c,d) - A(a,b) over ` `// all choices of indexes such  ` `// that both c > a and d > b. ` `function` `findMaxValue(``\$mat``) ` `{ ` `    ``global` `\$N``; ` `     `  `    ``// stores maximum value ` `    ``\$maxValue` `= PHP_INT_MIN; ` ` `  `    ``// maxArr[i][j] stores max  ` `    ``// of elements in matrix ` `    ``// from (i, j) to (N-1, N-1) ` `    ``\$maxArr``[``\$N``][``\$N``] = ``array``(); ` ` `  `    ``// last element of maxArr  ` `    ``// will be same's as of ` `    ``// the input matrix ` `    ``\$maxArr``[``\$N` `- 1][``\$N` `- 1] = ``\$mat``[``\$N` `- 1][``\$N` `- 1]; ` ` `  `    ``// preprocess last row ` `    ``\$maxv` `= ``\$mat``[``\$N` `- 1][``\$N` `- 1]; ``// Initialize max ` `    ``for` `(``\$j` `= ``\$N` `- 2; ``\$j` `>= 0; ``\$j``--) ` `    ``{ ` `        ``if` `(``\$mat``[``\$N` `- 1][``\$j``] > ``\$maxv``) ` `            ``\$maxv` `= ``\$mat``[``\$N` `- 1][``\$j``]; ` `        ``\$maxArr``[``\$N` `- 1][``\$j``] = ``\$maxv``; ` `    ``} ` ` `  `    ``// preprocess last column ` `    ``\$maxv` `= ``\$mat``[``\$N` `- 1][``\$N` `- 1]; ``// Initialize max ` `    ``for` `(``\$i` `= ``\$N` `- 2; ``\$i` `>= 0; ``\$i``--) ` `    ``{ ` `        ``if` `(``\$mat``[``\$i``][``\$N` `- 1] > ``\$maxv``) ` `            ``\$maxv` `= ``\$mat``[``\$i``][``\$N` `- 1]; ` `        ``\$maxArr``[``\$i``][``\$N` `- 1] = ``\$maxv``; ` `    ``} ` ` `  `    ``// preprocess rest of the ` `    ``// matrix from bottom ` `    ``for` `(``\$i` `= ``\$N` `- 2; ``\$i` `>= 0; ``\$i``--) ` `    ``{ ` `        ``for` `(``\$j` `= ``\$N` `- 2; ``\$j` `>= 0; ``\$j``--) ` `        ``{ ` `            ``// Update maxValue ` `            ``if` `(``\$maxArr``[``\$i` `+ 1][``\$j` `+ 1] -  ` `                ``\$mat``[``\$i``][``\$j``] > ``\$maxValue``) ` `                ``\$maxValue` `= ``\$maxArr``[``\$i` `+ 1][``\$j` `+ 1] -  ` `                            ``\$mat``[``\$i``][``\$j``]; ` ` `  `            ``// set maxArr (i, j) ` `            ``\$maxArr``[``\$i``][``\$j``] = max(``\$mat``[``\$i``][``\$j``], ` `                              ``max(``\$maxArr``[``\$i``][``\$j` `+ 1], ` `                                  ``\$maxArr``[``\$i` `+ 1][``\$j``])); ` `        ``} ` `    ``} ` ` `  `    ``return` `\$maxValue``; ` `} ` ` `  `// Driver Code ` `\$mat` `= ``array``(``array``(1, 2, -1, -4, -20), ` `             ``array``(-8, -3, 4, 2, 1), ` `             ``array``(3, 8, 6, 1, 3), ` `             ``array``(-4, -1, 1, 7, -6), ` `             ``array``(0, -4, 10, -5, 1) ` `                    ``); ` `echo` `"Maximum Value is "``.  ` `      ``findMaxValue(``\$mat``); ` ` `  `// This code is contributed  ` `// by ChitraNayal ` `?> `

Output:

`Maximum Value is 18`

If we are allowed to modify of the matrix, we can avoid using extra space and use input matrix instead.

Exercise: Print index (a, b) and (c, d) as well.

Matrix Matrix