Suma máxima de copa de cóctel en una array 2D

Posted on by Rudeus Greyrat

Dada una array 2D mat[][] , la tarea es encontrar la suma máxima de una copa de cóctel. 
 

A Cocktail glass is made of 6 cells in the following form:
X   X
  X
X X X

Ejemplos: 
 

Input: mat[][] = {
{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}}
Output: 11
Below is the cocktail glass with
maximum sum:
1   4 
  3
1 1 1
                                                      
Input: mat[][] = {
{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}}
Output: 12

Planteamiento: Es evidente de la definición de copa de cóctel que el número de filas y el número de columnas debe ser mayor o igual a 3. Si contamos el número total de copas de cóctel en una array, podemos decir que la cuenta es igual al recuento de las posibles celdas superiores izquierdas en una copa de cóctel. El número de celdas en la parte superior izquierda de una copa de cóctel es igual a (R – 2) * (C – 2). Por lo tanto, en una array el número total de copas de cóctel es (R – 2) * (C – 2) 
 

For mat[][] = {
{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}}
Possible cocktail glasses are:
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

Consideramos todas las celdas superiores izquierdas de copas de cóctel una por una. Para cada celda, calculamos la suma de la copa de cóctel formada por ella. Finalmente, devolvemos la suma máxima.
A continuación se muestra la implementación del enfoque anterior: 
 

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>
Producción: 

12

 

Complejidad de Tiempo: O(R * C)
Espacio Auxiliar: O(1), ya que no se ha tomado ningún espacio extra.

Publicación traducida automáticamente

Artículo escrito por Rajput-Ji y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *