Dada una array 2D, la tarea es encontrar la suma máxima de un reloj de arena.
An hour glass is made of 7 cells
in following form.
A B C
D
E F G
Ejemplos:
Input : 1 1 1 0 0
0 1 0 0 0
1 1 1 0 0
0 0 0 0 0
0 0 0 0 0
Output : 7
Below is the hour glass with
maximum sum:
1 1 1
1
1 1 1
Input : 0 3 0 0 0
0 1 0 0 0
1 1 1 0 0
0 0 2 4 4
0 0 0 2 4
Output : 11
Below is the hour glass with
maximum sum
1 0 0
4
0 2 4
Enfoque:
es evidente a partir de la definición del reloj de arena que el número de filas y el número de columnas debe ser igual a 3. Si contamos el número total de relojes de arena en una array, podemos decir que la cuenta es igual a la cuenta de posibles celdas superiores izquierdas en un reloj de arena. El número de celdas en la parte superior izquierda de un reloj de arena es igual a (R-2)*(C-2). Por tanto, en una array el número total de un reloj de arena es (R-2)*(C-2).
mat[][] = 2 3 0 0 0
0 1 0 0 0
1 1 1 0 0
0 0 2 4 4
0 0 0 2 0
Possible hour glass are :
2 3 0 3 0 0 0 0 0
1 0 0
1 1 1 1 1 0 1 0 0
0 1 0 1 0 0 0 0 0
1 1 0
0 0 2 0 2 4 2 4 4
1 1 1 1 1 0 1 0 0
0 2 4
0 0 0 0 0 2 0 2 0
Considere todas las celdas superiores izquierdas de los relojes de arena una por una. Para cada celda, calculamos la suma del reloj de arena formado por ella. Finalmente, devuelva la suma máxima.
A continuación se muestra la implementación de la idea anterior:
C++
// C++ program to find maximum sum of hour
// glass in matrix
#include<bits/stdc++.h>
using namespace std;
const int R = 5;
const int C = 5;
// Returns maximum sum of hour glass in ar[][]
int findMaxSum(int mat[R][C])
{
if (R<3 || C<3){
cout << "Not possible" << endl;
exit(0);
}
// Here loop runs (R-2)*(C-2) times considering
// different top left cells of hour glasses.
int max_sum = INT_MIN;
for (int i=0; i<R-2; i++)
{
for (int j=0; j<C-2; j++)
{
// Considering mat[i][j] as top left cell of
// hour glass.
int sum = (mat[i][j]+mat[i][j+1]+mat[i][j+2])+
(mat[i+1][j+1])+
(mat[i+2][j]+mat[i+2][j+1]+mat[i+2][j+2]);
// If previous sum is less then current sum then
// update new sum in max_sum
max_sum = max(max_sum, sum);
}
}
return max_sum;
}
// Driver code
int main()
{
int mat[][C] = {{1, 2, 3, 0, 0},
{0, 0, 0, 0, 0},
{2, 1, 4, 0, 0},
{0, 0, 0, 0, 0},
{1, 1, 0, 1, 0}};
int res = findMaxSum(mat);
cout << "Maximum sum of hour glass = "<< res << endl;
return 0;
}
//Code is modified by Susobhan Akhuli
C
/* C program to find the maximum
sum of hour glass in a Matrix */
#include <stdio.h>
#include <stdlib.h>
// Fixing the size of the matrix
// ( Here it is of the order 6
// x 6 )
#define R 5
#define C 5
// Function to find the maximum
// sum of the hour glass
int MaxSum(int arr[R][C])
{
int i, j, sum;
if (R<3 || C<3){
printf("Not Possible");
exit(0);
}
int max_sum
= -500000; /* Considering the matrix also contains
negative values , so initialized with
-50000. It can be any value but very
smaller.*/
// int max_sum=0 -> Initialize with 0 only if your
// matrix elements are positive
// Here loop runs (R-2)*(C-2) times considering
// different top left cells of hour glasses.
for (i = 0; i < R - 2; i++) {
for (j = 0; j < C - 2; j++) {
// Considering arr[i][j] as top left cell of
// hour glass.
sum = (arr[i][j] + arr[i][j + 1]
+ arr[i][j + 2])
+ (arr[i + 1][j + 1])
+ (arr[i + 2][j] + arr[i + 2][j + 1]
+ arr[i + 2][j + 2]);
// If previous sum is less then current sum then
// update new sum in max_sum
if (sum > max_sum)
max_sum = sum;
else
continue;
}
}
return max_sum;
}
// Driver Code
int main()
{
int arr[][C] = { { 1, 2, 3, 0, 0 },
{ 0, 0, 0, 0, 0 },
{ 2, 1, 4, 0, 0 },
{ 0, 0, 0, 0, 0 },
{ 1, 1, 0, 1, 0 } };
int res = MaxSum(arr);
printf("Maximum sum of hour glass = %d", res);
return 0;
}
// This code is written by Akshay Prakash
// Code is modified by Susobhan Akhuli
Java
// Java program to find maximum
// sum of hour glass in matrix
import java.io.*;
class GFG {
static int R = 5;
static int C = 5;
// Returns maximum sum of
// hour glass in ar[][]
static int findMaxSum(int [][]mat)
{
if (R < 3 || C < 3){
System.out.println("Not possible");
System.exit(0);
}
// Here loop runs (R-2)*(C-2)
// times considering different
// top left cells of hour glasses.
int max_sum = Integer.MIN_VALUE;
for (int i = 0; i < R - 2; i++)
{
for (int j = 0; j < C - 2; j++)
{
// Considering mat[i][j] as top
// left cell of hour glass.
int sum = (mat[i][j] + mat[i][j + 1] +
mat[i][j + 2]) + (mat[i + 1][j + 1]) +
(mat[i + 2][j] + mat[i + 2][j + 1] +
mat[i + 2][j + 2]);
// If previous sum is less then
// current sum then update
// new sum in max_sum
max_sum = Math.max(max_sum, sum);
}
}
return max_sum;
}
// Driver code
static public void main (String[] args)
{
int [][]mat = {{1, 2, 3, 0, 0},
{0, 0, 0, 0, 0},
{2, 1, 4, 0, 0},
{0, 0, 0, 0, 0},
{1, 1, 0, 1, 0}};
int res = findMaxSum(mat);
System.out.println("Maximum sum of hour glass = "+ res);
}
}
// This code is contributed by vt_m .
// Code is modified by Susobhan Akhuli
Python3
# Python 3 program to find the maximum
# sum of hour glass in a Matrix
# Fixing the size of the Matrix.
# Here it is of order 6 x 6
R = 5
C = 5
# Function to find the maximum sum of hour glass
def MaxSum(arr):
# Considering the matrix also contains
max_sum = -50000
# Negative values , so initialized with
# -50000. It can be any value but very
# smaller.
# max_sum=0 -> Initialize with 0 only if your
# matrix elements are positive
if(R < 3 or C < 3):
print("Not possible")
exit()
# Here loop runs (R-2)*(C-2) times considering
# different top left cells of hour glasses.
for i in range(0, R-2):
for j in range(0, C-2):
# Considering arr[i][j] as top
# left cell of hour glass.
SUM = (arr[i][j] + arr[i][j + 1] + arr[i][j + 2]) + (arr[i + 1][j + 1]) + (arr[i + 2][j] +
arr[i + 2][j + 1] + arr[i + 2][j + 2])
# If previous sum is less
# then current sum then
# update new sum in max_sum
if(SUM > max_sum):
max_sum = SUM
else:
continue
return max_sum
# Driver Code
arr = [[1, 2, 3, 0, 0],
[0, 0, 0, 0, 0],
[2, 1, 4, 0, 0],
[0, 0, 0, 0, 0],
[1, 1, 0, 1, 0]]
res = MaxSum(arr)
print(f"Maximum sum of hour glass = {res}")
# This code is written by Akshay Prakash
# Code is modified by Susobhan Akhuli
C#
// C# program to find maximum
// sum of hour glass in matrix
using System;
class GFG {
static int R = 5;
static int C = 5;
// Returns maximum sum of
// hour glass in ar[][]
static int findMaxSum(int [,]mat)
{
if (R < 3 || C < 3){
Console.WriteLine("Not possible");
Environment.Exit(0);
}
// Here loop runs (R-2)*(C-2)
// times considering different
// top left cells of hour glasses.
int max_sum = int.MinValue;
for (int i = 0; i < R - 2; i++)
{
for (int j = 0; j < C - 2; j++)
{
// Considering mat[i][j] as top
// left cell of hour glass.
int sum = (mat[i, j] + mat[i, j + 1] +
mat[i, j + 2]) + (mat[i + 1, j + 1]) +
(mat[i + 2, j] + mat[i + 2, j + 1] +
mat[i + 2, j + 2]);
// If previous sum is less then
// current sum then update
// new sum in max_sum
max_sum = Math.Max(max_sum, sum);
}
}
return max_sum;
}
// Driver code
static public void Main(String[] args)
{
int [,]mat = {{1, 2, 3, 0, 0},
{0, 0, 0, 0, 0},
{2, 1, 4, 0, 0},
{0, 0, 0, 0, 0},
{1, 1, 0, 1, 0}};
int res = findMaxSum(mat);
Console.WriteLine("Maximum sum of hour glass = "+ res);
}
}
// This code is contributed by vt_m .
// Code is modified by Susobhan Akhuli
PHP
<?php
// PHP program to find maximum sum
// of hour glass in matrix
$R = 5;
$C = 5;
// Returns maximum sum
// of hour glass in ar[][]
function findMaxSum($mat)
{
global $R; global $C;
if ($R < 3 || $C < 3){
exit("Not possible");
}
// Here loop runs (R-2)*(C-2) times considering
// different top left cells of hour glasses.
$max_sum = PHP_INT_MIN;
for ($i = 0; $i < ($R - 2); $i++)
{
for ($j = 0; $j < ($C - 2); $j++)
{
// Considering mat[i][j] as
// top left cell of hour glass.
$sum = ($mat[$i][$j] + $mat[$i][$j + 1] +
$mat[$i][$j + 2]) +
($mat[$i + 1][$j + 1]) +
($mat[$i + 2][$j] +
$mat[$i + 2][$j + 1] +
$mat[$i + 2][$j + 2]);
// If previous sum is less than current sum
// then update new sum in max_sum
$max_sum = max($max_sum, $sum);
}
}
return $max_sum;
}
// Driver code
$mat = array(array(1, 2, 3, 0, 0),
array(0, 0, 0, 0, 0),
array(2, 1, 4, 0, 0),
array(0, 0, 0, 0, 0),
array(1, 1, 0, 1, 0));
$res = findMaxSum($mat);
echo "Maximum sum of hour glass = ",$res, "\n";
// This code is contributed by ajit.
// Code is modified by Susobhan Akhuli
?>
Javascript
<script>
// Javascript program to find maximum
// sum of hour glass in matrix
let R = 5;
let C = 5;
// Returns maximum sum of
// hour glass in ar[][]
function findMaxSum(mat)
{
if (R < 3 || C < 3){
document.write("Not possible");
process.exit(0);
}
// Here loop runs (R-2)*(C-2)
// times considering different
// top left cells of hour glasses.
let max_sum = Number.MIN_VALUE;
for (let i = 0; i < R - 2; i++)
{
for (let j = 0; j < C - 2; j++)
{
// Considering mat[i][j] as top
// left cell of hour glass.
let sum = (mat[i][j] + mat[i][j + 1] +
mat[i][j + 2]) + (mat[i + 1][j + 1]) +
(mat[i + 2][j] + mat[i + 2][j + 1] +
mat[i + 2][j + 2]);
// If previous sum is less then
// current sum then update
// new sum in max_sum
max_sum = Math.max(max_sum, sum);
}
}
return max_sum;
}
let mat = [[1, 2, 3, 0, 0],
[0, 0, 0, 0, 0],
[2, 1, 4, 0, 0],
[0, 0, 0, 0, 0],
[1, 1, 0, 1, 0]];
let res = findMaxSum(mat);
document.write("Maximum sum of hour glass = " + res);
</script>
Producción
Maximum sum of hour glass = 13
Complejidad temporal: O(R x C).
Espacio Auxiliar: O(1)
Referencia:
http://stackoverflow.com/questions/38019861/hourglass-sum-in-2d-array
Este artículo es una contribución de AKSHAY PRAKASH . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA