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 <bits/stdc++.h> 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
<?php // A Naive method to find maximum // value of $mat[d][e] - ma[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. 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 <bits/stdc++.h> 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
<?php // An efficient method to find // maximum value of mat[d] - ma[a][b] // such that c > 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.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
leave a comment
0 Comments