Максимальная сумма коктейльного бокала в 2D матрице
Для двумерного матричного мата [] [] задача состоит в том, чтобы найти максимальную сумму коктейльного бокала.
Бокал для коктейлей состоит из 6 ячеек и имеет следующий вид: XX Икс XXX
Примеры:
Ввод: мат [] [] = { {1, 0, 4, 0, 0}, {0, 3, 0, 0, 0}, {1, 1, 1, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}} Выход: 11 Ниже представлен коктейльный бокал с максимальная сумма: 1 4 3 1 1 1 Ввод: мат [] [] = { {0, 3, 0, 6, 0}, {0, 1, 1, 0, 0}, {1, 1, 1, 0, 0}, {0, 0, 2, 0, 1}, {0, 2, 0, 1, 3}} Выход: 12
Подход: Из определения коктейльного бокала очевидно, что количество строк и количество столбцов должно быть больше или равно 3. Если мы посчитаем общее количество коктейльных бокалов в матрице, мы можем сказать, что количество равно к количеству возможных верхних левых ячеек в бокале для коктейля. Количество верхних левых ячеек в бокале для коктейля равно (R - 2) * (C - 2). Следовательно, в матрице общее количество коктейльных бокалов равно (R - 2) * (C - 2).
Для мат [] [] = { {0, 3, 0, 6, 0}, {0, 1, 1, 0, 0}, {1, 1, 1, 0, 0}, {0, 0, 2, 0, 1}, {0, 2, 0, 1, 3}} Возможные коктейльные бокалы: 0 0 3 6 0 0 1 1 0 1 1 1 1 1 0 1 0 0 0 1 1 0 1 0 1 1 0 0 0 2 0 2 0 2 0 1 1 1 1 0 1 0 0 2 0 0 2 0 2 0 1 0 1 3
We consider all top left cells of cocktail glasses one by one. For every cell, we compute the sum of the cocktail glass formed by it. Finally, we return the maximum sum.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; const int R = 5; const int C = 5; // Function to return the maximum sum // of a cocktail glass int findMaxCock( int ar[R][C]) { // If no cocktail glass is possible if (R < 3 || C < 3) return -1; // Initialize max_sum with the mini int max_sum = INT_MIN; // Here loop runs (R-2)*(C-2) times considering // different top left cells of cocktail glasses for ( int i = 0; i < R - 2; i++) { for ( int j = 0; j < C - 2; j++) { // Considering mat[i][j] as the top left // cell of the cocktail glass int sum = (ar[i][j] + ar[i][j + 2]) + (ar[i + 1][j + 1]) + (ar[i + 2][j] + ar[i + 2][j + 1] + ar[i + 2][j + 2]); // Update the max_sum max_sum = max(max_sum, sum); } } return max_sum; } // Driver code int main() { int ar[][C] = { { 0, 3, 0, 6, 0 }, { 0, 1, 1, 0, 0 }, { 1, 1, 1, 0, 0 }, { 0, 0, 2, 0, 1 }, { 0, 2, 0, 1, 3 } }; cout << findMaxCock(ar); return 0; } |
Java
// Java implementation of the approach class GFG { static int R = 5 ; static int C = 5 ; // Function to return the maximum sum // of a cocktail glass static int findMaxCock( int ar[][]) { // If no cocktail glass is possible if (R < 3 || C < 3 ) return - 1 ; // Initialize max_sum with the mini int max_sum = Integer.MIN_VALUE; // Here loop runs (R-2)*(C-2) times considering // different top left cells of cocktail glasses for ( int i = 0 ; i < R - 2 ; i++) { for ( int j = 0 ; j < C - 2 ; j++) { // Considering mat[i][j] as the top left // cell of the cocktail glass int sum = (ar[i][j] + ar[i][j + 2 ]) + (ar[i + 1 ][j + 1 ]) + (ar[i + 2 ][j] + ar[i + 2 ][j + 1 ] + ar[i + 2 ][j + 2 ]); // Update the max_sum max_sum = Math.max(max_sum, sum); } } return max_sum; } // Driver code public static void main (String[] args) { int ar[][] = { { 0 , 3 , 0 , 6 , 0 }, { 0 , 1 , 1 , 0 , 0 }, { 1 , 1 , 1 , 0 , 0 }, { 0 , 0 , 2 , 0 , 1 }, { 0 , 2 , 0 , 1 , 3 } }; System.out.println(findMaxCock(ar)); } } // This code is contributed by mits |
Python3
# Python 3 implementation of the approach import sys R = 5 C = 5 # Function to return the maximum sum # of a cocktail glass def findMaxCock(ar): # If no cocktail glass is possible if (R < 3 or C < 3 ): return - 1 # Initialize max_sum with the mini max_sum = - sys.maxsize - 1 # Here loop runs (R-2)*(C-2) times considering # different top left cells of cocktail glasses for i in range (R - 2 ): for j in range (C - 2 ): # Considering mat[i][j] as the top left # cell of the cocktail glass sum = ((ar[i][j] + ar[i][j + 2 ]) + (ar[i + 1 ][j + 1 ]) + (ar[i + 2 ][j] + ar[i + 2 ][j + 1 ] + ar[i + 2 ][j + 2 ])) # Update the max_sum max_sum = max (max_sum, sum ) return max_sum; # Driver code if __name__ = = "__main__" : ar = [[ 0 , 3 , 0 , 6 , 0 ], [ 0 , 1 , 1 , 0 , 0 ], [ 1 , 1 , 1 , 0 , 0 ], [ 0 , 0 , 2 , 0 , 1 ], [ 0 , 2 , 0 , 1 , 3 ]] print (findMaxCock(ar)) # This code is contributed by # Surendra_Gangwar |
C#
// C# implementation of the approach using System; class GFG { static int R = 5; static int C = 5; // Function to return the maximum sum // of a cocktail glass static int findMaxCock( int [,]ar) { // If no cocktail glass is possible if (R < 3 || C < 3) return -1; // Initialize max_sum with the mini int max_sum = int .MinValue; // Here loop runs (R-2)*(C-2) times considering // different top left cells of cocktail glasses for ( int i = 0; i < R - 2; i++) { for ( int j = 0; j < C - 2; j++) { // Considering mat[i][j] as the top left // cell of the cocktail glass int sum = (ar[i,j] + ar[i,j + 2]) + (ar[i + 1,j + 1]) + (ar[i + 2,j] + ar[i + 2,j + 1] + ar[i + 2,j + 2]); // Update the max_sum max_sum = Math.Max(max_sum, sum); } } return max_sum; } // Driver code public static void Main () { int [,]ar = { { 0, 3, 0, 6, 0 }, { 0, 1, 1, 0, 0 }, { 1, 1, 1, 0, 0 }, { 0, 0, 2, 0, 1 }, { 0, 2, 0, 1, 3 } }; Console.WriteLine(findMaxCock(ar)); } } // This code is contributed by Ryuga |
PHP
<?PHP // PHP implementation of the approach $R = 5; $C = 5; // Function to return the maximum sum // of a cocktail glass function findMaxCock( $ar ) { global $R , $C ; // If no cocktail glass is possible if ( $R < 3 || $C < 3) return -1; // Initialize max_sum with the mini $max_sum = PHP_INT_MIN; // Here loop runs (R-2)*(C-2) times considering // different top left cells of cocktail glasses for ( $i = 0; $i < $R - 2; $i ++) { for ( $j = 0; $j < $C - 2; $j ++) { // Considering mat[i][j] as the top left // cell of the cocktail glass $sum = ( $ar [ $i ][ $j ] + $ar [ $i ][ $j + 2]) + ( $ar [ $i + 1][ $j + 1]) + ( $ar [ $i + 2][ $j ] + $ar [ $i + 2][ $j + 1] + $ar [ $i + 2][ $j + 2]); // Update the max_sum $max_sum = max( $max_sum , $sum ); } } return $max_sum ; } // Driver code $ar = array ( array ( 0, 3, 0, 6, 0 ), array ( 0, 1, 1, 0, 0 ), array ( 1, 1, 1, 0, 0 ), array ( 0, 0, 2, 0, 1 ), array ( 0, 2, 0, 1, 3 )); echo (findMaxCock( $ar )); // This code is contributed by Code_Mech ?> |
Javascript
<script> // Javascript implementation of the approach var R = 5; var C = 5; // Function to return the maximum sum // of a cocktail glass function findMaxCock(ar) { // If no cocktail glass is possible if (R < 3 || C < 3) return -1; // Initialize max_sum with the mini var max_sum = -1000000000; // Here loop runs (R-2)*(C-2) times considering // different top left cells of cocktail glasses for ( var i = 0; i < R - 2; i++) { for ( var j = 0; j < C - 2; j++) { // Considering mat[i][j] as the top left // cell of the cocktail glass var sum = (ar[i][j] + ar[i][j + 2]) + (ar[i + 1][j + 1]) + (ar[i + 2][j] + ar[i + 2][j + 1] + ar[i + 2][j + 2]); // Update the max_sum max_sum = Math.max(max_sum, sum); } } return max_sum; } // Driver code ar = [ [ 0, 3, 0, 6, 0 ], [ 0, 1, 1, 0, 0 ], [ 1, 1, 1, 0, 0 ], [ 0, 0, 2, 0, 1 ], [ 0, 2, 0, 1, 3 ] ]; document.write(findMaxCock(ar)); </script> |
12
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.