给定一个方阵，求其四个相邻元素的最大乘积。矩阵的相邻元素可以是上、下、左、右、对角或反对角。四个或四个以上的数字应该相邻。
null
注： n应大于或等于4，即n>=4
例如：
Input : n = 4 {{6, 2, 3 4}, {5, 4, 3, 1}, {7, 4, 5, 6}, {8, 3, 1, 0}}Output : 1680 Explanation:Multiplication of 6 5 7 8 produces maximumresult and all element are adjacent to each other in one directionInput : n = 5 {{1, 2, 3, 4, 5}, {6, 7, 8, 9, 1}, {2, 3, 4, 5, 6}, {7, 8, 9, 1, 0}, {9, 6, 4, 2, 3}}Output: 3024Explanation:Multiplication of 6 7 8 9 produces maximum result and all elements are adjacent toeach other in one direction.
提问：托莱索
方法：
- 将每行中彼此相邻的4个元素分组，并计算其最大结果。
- 将每列中彼此相邻的4个元素分组，并计算其最大结果。
- 将对角线上相邻的4个元素分组，并计算其最大结果。
- 将4个在反对角线上相邻的元素分组，并计算其最大结果。
- 比较所有计算的最大结果。
以下是上述方法的实施情况：
C++
// C++ program to find out the maximum product // in the matrix which four elements are // adjacent to each other in one direction #include <bits/stdc++.h> using namespace std; const int n = 5; // function to find max product int FindMaxProduct( int arr[][n], int n) { int max = 0, result; // iterate the rows. for ( int i = 0; i < n; i++) { // iterate the columns. for ( int j = 0; j < n; j++) { // check the maximum product // in horizontal row. if ((j - 3) >= 0) { result = arr[i][j] * arr[i][j - 1] * arr[i][j - 2] * arr[i][j - 3]; if (max < result) max = result; } // check the maximum product // in vertical row. if ((i - 3) >= 0) { result = arr[i][j] * arr[i - 1][j] * arr[i - 2][j] * arr[i - 3][j]; if (max < result) max = result; } // check the maximum product in // diagonal (going through down - right) if ((i - 3) >= 0 && (j - 3) >= 0) { result = arr[i][j] * arr[i - 1][j - 1] * arr[i - 2][j - 2] * arr[i - 3][j - 3]; if (max < result) max = result; } // check the maximum product in // diagonal (going through up - right) if ((i - 3) >= 0 && (j - 1) <= 0) { result = arr[i][j] * arr[i - 1][j + 1] * arr[i - 2][j + 2] * arr[i - 3][j + 3]; if (max < result) max = result; } } } return max; } // Driver code int main() { /* int arr[][4] = {{6, 2, 3, 4}, {5, 4, 3, 1}, {7, 4, 5, 6}, {8, 3, 1, 0}};*/ /* int arr[][5] = {{1, 2, 1, 3, 4}, {5, 6, 3, 9, 2}, {7, 8, 8, 1, 2}, {1, 0, 7, 9, 3}, {3, 0, 8, 4, 9}};*/ int arr[][5] = {{1, 2, 3, 4, 5}, {6, 7, 8, 9, 1}, {2, 3, 4, 5, 6}, {7, 8, 9, 1, 0}, {9, 6, 4, 2, 3}}; cout << FindMaxProduct(arr, n); return 0; } |
JAVA
// Java program to find out the // maximum product in the matrix // which four elements are adjacent // to each other in one direction class GFG { static final int n = 5 ; // function to find max product static int FindMaxProduct( int arr[][], int n) { int max = 0 , result; // iterate the rows. for ( int i = 0 ; i < n; i++) { // iterate the columns. for ( int j = 0 ; j < n; j++) { // check the maximum product // in horizontal row. if ((j - 3 ) >= 0 ) { result = arr[i][j] * arr[i][j - 1 ] * arr[i][j - 2 ] * arr[i][j - 3 ]; if (max < result) max = result; } // check the maximum product // in vertical row. if ((i - 3 ) >= 0 ) { result = arr[i][j] * arr[i - 1 ][j] * arr[i - 2 ][j] * arr[i - 3 ][j]; if (max < result) max = result; } // check the maximum product in // diagonal (going through down - right) if ((i - 3 ) >= 0 && (j - 3 ) >= 0 ) { result = arr[i][j] * arr[i - 1 ][j - 1 ] * arr[i - 2 ][j - 2 ] * arr[i - 3 ][j - 3 ]; if (max < result) max = result; } // check the maximum product in // diagonal (going through up - right) if ((i - 3 ) >= 0 && (j - 1 ) <= 0 ) { result = arr[i][j] * arr[i - 1 ][j + 1 ] * arr[i - 2 ][j + 2 ] * arr[i - 3 ][j + 3 ]; if (max < result) max = result; } } } return max; } // Driver code public static void main(String[] args) { /* int arr[][4] = {{6, 2, 3, 4}, {5, 4, 3, 1}, {7, 4, 5, 6}, {8, 3, 1, 0}};*/ /* int arr[][5] = {{1, 2, 1, 3, 4}, {5, 6, 3, 9, 2}, {7, 8, 8, 1, 2}, {1, 0, 7, 9, 3}, {3, 0, 8, 4, 9}};*/ int arr[][] = { { 1 , 2 , 3 , 4 , 5 }, { 6 , 7 , 8 , 9 , 1 }, { 2 , 3 , 4 , 5 , 6 }, { 7 , 8 , 9 , 1 , 0 }, { 9 , 6 , 4 , 2 , 3 } }; System.out.print(FindMaxProduct(arr, n)); } } // This code is contributed by Anant Agarwal. |
Python3
# Python3 program to find out the maximum # product in the matrix which four elements # are adjacent to each other in one direction n = 5 # function to find max product def FindMaxProduct(arr, n): max = 0 # iterate the rows. for i in range (n): # iterate the columns. for j in range ( n): # check the maximum product # in horizontal row. if ((j - 3 ) > = 0 ): result = (arr[i][j] * arr[i][j - 1 ] * arr[i][j - 2 ] * arr[i][j - 3 ]) if ( max < result): max = result # check the maximum product # in vertical row. if ((i - 3 ) > = 0 ) : result = (arr[i][j] * arr[i - 1 ][j] * arr[i - 2 ][j] * arr[i - 3 ][j]) if ( max < result): max = result # check the maximum product in # diagonal going through down - right if ((i - 3 ) > = 0 and (j - 3 ) > = 0 ): result = (arr[i][j] * arr[i - 1 ][j - 1 ] * arr[i - 2 ][j - 2 ] * arr[i - 3 ][j - 3 ]) if ( max < result): max = result # check the maximum product in # diagonal going through up - right if ((i - 3 ) > = 0 and (j - 1 ) < = 0 ): result = (arr[i][j] * arr[i - 1 ][j + 1 ] * arr[i - 2 ][j + 2 ] * arr[i - 3 ][j + 3 ]) if ( max < result): max = result return max # Driver code if __name__ = = "__main__" : # int arr[][4] = {{6, 2, 3, 4}, # {5, 4, 3, 1}, # {7, 4, 5, 6}, # {8, 3, 1, 0}}; # int arr[][5] = {{1, 2, 1, 3, 4}, # {5, 6, 3, 9, 2}, # {7, 8, 8, 1, 2}, # {1, 0, 7, 9, 3}, # {3, 0, 8, 4, 9}}; arr = [[ 1 , 2 , 3 , 4 , 5 ], [ 6 , 7 , 8 , 9 , 1 ], [ 2 , 3 , 4 , 5 , 6 ], [ 7 , 8 , 9 , 1 , 0 ], [ 9 , 6 , 4 , 2 , 3 ]] print (FindMaxProduct(arr, n)) # This code is contributed by ita_c |
C#
// C# program to find out the // maximum product in the matrix // which four elements are adjacent // to each other in one direction using System; public class GFG { static int n = 5; // Function to find max product static int FindMaxProduct( int [, ] arr, int n) { int max = 0, result; // iterate the rows for ( int i = 0; i < n; i++) { // iterate the columns for ( int j = 0; j < n; j++) { // check the maximum product // in horizontal row. if ((j - 3) >= 0) { result = arr[i, j] * arr[i, j - 1] * arr[i, j - 2] * arr[i, j - 3]; if (max < result) max = result; } // check the maximum product // in vertical row. if ((i - 3) >= 0) { result = arr[i, j] * arr[i - 1, j] * arr[i - 2, j] * arr[i - 3, j]; if (max < result) max = result; } // check the maximum product in // diagonal going through down - right if ((i - 3) >= 0 && (j - 3) >= 0) { result = arr[i, j] * arr[i - 1, j - 1] * arr[i - 2, j - 2] * arr[i - 3, j - 3]; if (max < result) max = result; } // check the maximum product in // diagonal going through up - right if ((i - 3) >= 0 && (j - 1) <= 0) { result = arr[i, j] * arr[i - 1, j + 1] * arr[i - 2, j + 2] * arr[i - 3, j + 3]; if (max < result) max = result; } } } return max; } // Driver Code static public void Main() { int [, ] arr = { { 1, 2, 3, 4, 5 }, { 6, 7, 8, 9, 1 }, { 2, 3, 4, 5, 6 }, { 7, 8, 9, 1, 0 }, { 9, 6, 4, 2, 3 } }; Console.Write(FindMaxProduct(arr, n)); } } // This code is contributed by Shrikant13 |
PHP
<?php // PHP program to find out the maximum product // in the matrix which four elements are // adjacent to each other in one direction $n = 5; // function to find max product function FindMaxProduct( $arr , $n ) { $max = 0; $result ; // iterate the rows. for ( $i = 0; $i < $n ; $i ++) { // iterate the columns. for ( $j = 0; $j < $n ; $j ++) { // check the maximum product // in horizontal row. if (( $j - 3) >= 0) { $result = $arr [ $i ][ $j ] * $arr [ $i ][ $j - 1] * $arr [ $i ][ $j - 2] * $arr [ $i ][ $j - 3]; if ( $max < $result ) $max = $result ; } // check the maximum product // in vertical row. if (( $i - 3) >= 0) { $result = $arr [ $i ][ $j ] * $arr [ $i - 1][ $j ] * $arr [ $i - 2][ $j ] * $arr [ $i - 3][ $j ]; if ( $max < $result ) $max = $result ; } // check the maximum product in // diagonal going through down - right if (( $i - 3) >= 0 and ( $j - 3) >= 0) { $result = $arr [ $i ][ $j ] * $arr [ $i - 1][ $j - 1] * $arr [ $i - 2][ $j - 2] * $arr [ $i - 3][ $j - 3]; if ( $max < $result ) $max = $result ; } // check the maximum product in // diagonal going through up - right if (( $i - 3) >= 0 and ( $j - 1) <= 0) { $result = $arr [ $i ][ $j ] * $arr [ $i - 1][ $j + 1] * $arr [ $i - 2][ $j + 2] * $arr [ $i - 3][ $j + 3]; if ( $max < $result ) $max = $result ; } } } return $max ; } // Driver Code $arr = array ( array (1, 2, 3, 4, 5), array (6, 7, 8, 9, 1), array (2, 3, 4, 5, 6), array (7, 8, 9, 1, 0), array (9, 6, 4, 2, 3)); echo FindMaxProduct( $arr , $n ); // This code is contributed by anuj_67. ?> |
Javascript
<script> // Javascript program to find out the // maximum product in the matrix // which four elements are adjacent // to each other in one direction let n = 5; // function to find max product function FindMaxProduct(arr,n) { let max = 0, result; // iterate the rows. for (let i = 0; i < n; i++) { // iterate the columns. for (let j = 0; j < n; j++) { // check the maximum product // in horizontal row. if ((j - 3) >= 0) { result = arr[i][j] * arr[i][j - 1] * arr[i][j - 2] * arr[i][j - 3]; if (max < result) max = result; } // check the maximum product // in vertical row. if ((i - 3) >= 0) { result = arr[i][j] * arr[i - 1][j] * arr[i - 2][j] * arr[i - 3][j]; if (max < result) max = result; } // check the maximum product in // diagonal (going through down - right) if ((i - 3) >= 0 && (j - 3) >= 0) { result = arr[i][j] * arr[i - 1][j - 1] * arr[i - 2][j - 2] * arr[i - 3][j - 3]; if (max < result) max = result; } // check the maximum product in // diagonal (going through up - right) if ((i - 3) >= 0 && (j - 1) <= 0) { result = arr[i][j] * arr[i - 1][j + 1] * arr[i - 2][j + 2] * arr[i - 3][j + 3]; if (max < result) max = result; } } } return max; } // Driver code /* int arr[][4] = {{6, 2, 3, 4}, {5, 4, 3, 1}, {7, 4, 5, 6}, {8, 3, 1, 0}};*/ /* int arr[][5] = {{1, 2, 1, 3, 4}, {5, 6, 3, 9, 2}, {7, 8, 8, 1, 2}, {1, 0, 7, 9, 3}, {3, 0, 8, 4, 9}};*/ let arr = [[ 1, 2, 3, 4, 5 ], [ 6, 7, 8, 9, 1 ], [ 2, 3, 4, 5, 6 ], [ 7, 8, 9, 1, 0 ], [ 9, 6, 4, 2, 3 ]]; document.write(FindMaxProduct(arr, n)); // This code is contributed by sravan kumar </script> |
输出
3024
对于行相邻单元，我们可以使用滑动窗口来推广该方法。
注： 矩阵中的所有元素都必须是非零的。
另一种方法：
- 对于每一行，创建一个大小为k的窗口。将k个相邻元素的乘积作为窗口乘积（wp）。
- 从k到（行大小）迭代行，通过滑动窗口方法，找到最大乘积。注：（行大小）>=k。
- 将最大乘积分配给全局最大乘积。
以下是上述方法的实施情况：
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; int maxPro( int a[6][5], int n, int m, int k) { int maxi(1), mp(1); for ( int i = 0; i < n; ++i) { // Window Product for each row. int wp(1); for ( int l = 0; l < k; ++l) { wp *= a[i][l]; } // Maximum window product for each row mp = wp; for ( int j = k; j < m; ++j) { wp = wp * a[i][j] / a[i][j - k]; // Global maximum window product maxi = max(maxi,max(mp,wp)); } } return maxi; } // Driver Code int main() { int n = 6, m = 5, k = 4; int a[6][5] = { { 1, 2, 3, 4, 5 }, { 6, 7, 8, 9, 1 }, { 2, 3, 4, 5, 6 }, { 7, 8, 9, 1, 0 }, { 9, 6, 4, 2, 3 }, { 1, 1, 2, 1, 1 } }; cout << maxPro(a, n, m, k); return 0; } |
JAVA
// Java implementation of the above approach import java.io.*; class GFG { public static int maxPro( int [][] a, int n, int m, int k) { int maxi = 1 , mp = 1 ; for ( int i = 0 ; i < n; ++i) { // Window Product for each row. int wp = 1 ; for ( int l = 0 ; l < k; ++l) { wp *= a[i][l]; } // Maximum window product for each row mp = wp; for ( int j = k; j < m; ++j) { wp = wp * a[i][j] / a[i][j - k]; // Global maximum // window product maxi = Math.max( maxi, Math.max(mp, wp)); } } return maxi; } // Driver Code public static void main(String[] args) { int n = 6 , m = 5 , k = 4 ; int [][] a = new int [][] { { 1 , 2 , 3 , 4 , 5 }, { 6 , 7 , 8 , 9 , 1 }, { 2 , 3 , 4 , 5 , 6 }, { 7 , 8 , 9 , 1 , 0 }, { 9 , 6 , 4 , 2 , 3 }, { 1 , 1 , 2 , 1 , 1 } }; // Function call int maxpro = maxPro(a, n, m, k); System.out.println(maxpro); } } |
Python3
# Python implementation of the above approach def maxPro(a,n,m,k): maxi = 1 mp = 1 for i in range (n): # Window Product for each row. wp = 1 for l in range (k): wp * = a[i][l] # Maximum window product for each row mp = wp for j in range (k,m): wp = wp * a[i][j] / a[i][j - k] # Global maximum # window product maxi = max ( maxi, max (mp, wp)) return maxi # Driver Code n = 6 m = 5 k = 4 a = [[ 1 , 2 , 3 , 4 , 5 ], [ 6 , 7 , 8 , 9 , 1 ], [ 2 , 3 , 4 , 5 , 6 ], [ 7 , 8 , 9 , 1 , 0 ], [ 9 , 6 , 4 , 2 , 3 ], [ 1 , 1 , 2 , 1 , 1 ]] # Function call maxpro = maxPro(a, n, m, k) print (maxpro) # This code is contributed by ab2127 |
C#
// C# implementation of the above approach using System; class GFG{ public static int maxPro( int [,] a, int n, int m, int k) { int maxi = 1, mp = 1; for ( int i = 0; i < n; ++i) { // Window Product for each row. int wp = 1; for ( int l = 0; l < k; ++l) { wp *= a[i, l]; } // Maximum window product for each row mp = wp; for ( int j = k; j < m; ++j) { wp = wp * a[i, j] / a[i, j - k]; // Global maximum // window product maxi = Math.Max(maxi, Math.Max(mp, wp)); } } return maxi; } // Driver Code static public void Main() { int n = 6, m = 5, k = 4; int [,] a = {{ 1, 2, 3, 4, 5 }, { 6, 7, 8, 9, 1 }, { 2, 3, 4, 5, 6 }, { 7, 8, 9, 1, 0 }, { 9, 6, 4, 2, 3 }, { 1, 1, 2, 1, 1 }}; // Function call int maxpro = maxPro(a, n, m, k); Console.WriteLine(maxpro); } } // This code is contributed by avanitrachhadiya2155 |
Javascript
<script> // Javascript implementation of the above approach function maxPro(a,n,m,k) { let maxi = 1, mp = 1; for (let i = 0; i < n; ++i) { // Window Product for each row. let wp = 1; for (let l = 0; l < k; ++l) { wp *= a[i][l]; } // Maximum window product for each row mp = wp; for (let j = k; j < m; ++j) { wp = wp * a[i][j] / a[i][j - k]; // Global maximum // window product maxi = Math.max( maxi, Math.max(mp, wp)); } } return maxi; } // Driver Code let n = 6, m = 5, k = 4; let a=[[1, 2, 3, 4, 5 ], [ 6, 7, 8, 9, 1 ], [ 2, 3, 4, 5, 6 ], [ 7, 8, 9, 1, 0 ], [ 9, 6, 4, 2, 3 ], [ 1, 1, 2, 1, 1 ]] // Function call let maxpro = maxPro(a, n, m, k); document.write(maxpro); // This code is contributed by rag2127 </script> |
输出
3024
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
