给定一个n x n矩阵mat[n][n]的整数，求mat（c，d）–mat（a，b）在所有索引选择上的最大值，使c>a和d>b。 例子：
null
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: 18The maximum value is 18 as mat[4][2] - mat[1][0] = 18 has maximum difference.
程序应该只对矩阵进行一次遍历。i、 e.预期时间复杂度为O（n 2. ) A. 简单解决方案 就是使用暴力。对于矩阵中的所有值mat（a，b），我们发现mat（c，d）具有最大值，例如c>a和d>b，并不断更新迄今为止发现的最大值。我们最终返回最大值。 下面是它的实现。
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 ?> |
Javascript
<script> // A Naive method to find maximum value of mat1[d][e] // - ma[a][b] such that d > a and e > b // 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(N,mat) { // stores maximum value let maxValue = Number.MIN_VALUE; // Consider all possible pairs mat[a][b] and // mat1[d][e] for (let a = 0; a < N - 1; a++) for (let b = 0; b < N - 1; b++) for (let d = a + 1; d < N; d++) for (let 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 let N = 5; let 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 ]]; document.write( "Maximum Value is " +findMaxValue(N,mat)); // This code is contributed by rag2127 </script> |
输出：
Maximum Value is 18
上述程序在O（n^4）时间内运行，这与O（n^2）的预期时间复杂度相差甚远 一 有效解决方案 使用额外的空间。我们对矩阵进行预处理，使索引（i，j）存储矩阵中从（i，j）到（N-1，N-1）的元素的最大值，并在这个过程中不断更新迄今为止发现的最大值。我们最终返回最大值。
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 ?> |
Javascript
<script> // An efficient method to find maximum value of mat1[d] // - ma[a][b] such that c > a and d > b // 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(N,mat) { // stores maximum value let maxValue = Number.MIN_VALUE; // maxArr[i][j] stores max of elements in matrix // from (i, j) to (N-1, N-1) let maxArr= new Array(N); for (let i = 0; i < N; i++) { maxArr[i]= new Array(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 let maxv = mat[N-1][N-1]; // Initialize max for (let 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 (let 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 (let i = N-2; i >= 0; i--) { for (let 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 let N = 5; let 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 ]]; document.write( "Maximum Value is " + findMaxValue(N,mat)); // This code is contributed by avanitrachhadiya2155 </script> |
输出：
Maximum Value is 18
如果允许我们修改矩阵的形式，我们可以避免使用额外的空间，而是使用输入矩阵。 练习： 打印索引（a，b）和（c，d）。 本文由 阿迪蒂亚·戈尔 .如果你喜欢GeekSforgek，并且想贡献自己的力量，你也可以写一篇文章，并将文章邮寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
