Dada una array N x N, determine el K máximo tal que K x K sea una subarray con todos los elementos iguales, es decir, todos los elementos en esta subarray deben ser iguales.
Restricciones:
- 1 <= norte <= 1000
- 0 <= UN yo , j <= 10 9
Ejemplos:
Input : a[][] = {{2, 3, 3},
{2, 3, 3},
{2, 2, 2}}
Output : 2
Explanation: A 2x2 matrix is formed from index
A0,1 to A1,2
Input : a[][] = {{9, 9, 9, 8},
{9, 9, 9, 6},
{9, 9, 9, 3},
{2, 2, 2, 2}
Output : 3
Explanation : A 3x3 matrix is formed from index
A0,0 to A2,2
Método I (enfoque ingenuo):
Podemos encontrar fácilmente todas las subarrays cuadradas en el tiempo O(n 3 ) y verificar si cada subarray contiene elementos iguales o no en el tiempo O(n 2 ), lo que hace que el tiempo total de ejecución del algoritmo sea O (n5 ) .
Método II (programación dinámica):
para cada celda (i, j), almacenamos el valor más grande de K de modo que K x K es una subarray con todos los elementos iguales y la posición de (i, j) es el elemento más abajo a la derecha .
Y DP i,j depende de {DP i-1, j , DP i, j-1 , DP i-1, j-1 }
If Ai, j is equal to {Ai-1, j, Ai, j-1, Ai-1, j-1},
all the three values:
DPi, j = min(DPi-1, j, DPi, j-1, DPi-1, j-1) + 1
Else
DPi, j = 1 // Matrix Size 1
The answer would be the maximum of all DPi, j's
A continuación se muestra la implementación de los pasos anteriores.
C++
// C++ program to find maximum K such that K x K
// is a submatrix with equal elements.
#include<bits/stdc++.h>
#define Row 6
#define Col 6
using namespace std;
// Returns size of the largest square sub-matrix
// with all same elements.
int largestKSubmatrix(int a[][Col])
{
int dp[Row][Col];
memset(dp, sizeof(dp), 0);
int result = 0;
for (int i = 0 ; i < Row ; i++)
{
for (int j = 0 ; j < Col ; j++)
{
// If elements is at top row or first
// column, it wont form a square
// matrix's bottom-right
if (i == 0 || j == 0)
dp[i][j] = 1;
else
{
// Check if adjacent elements are equal
if (a[i][j] == a[i-1][j] &&
a[i][j] == a[i][j-1] &&
a[i][j] == a[i-1][j-1] )
dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]),
dp[i-1][j-1] ) + 1;
// If not equal, then it will form a 1x1
// submatrix
else dp[i][j] = 1;
}
// Update result at each (i,j)
result = max(result, dp[i][j]);
}
}
return result;
}
// Driven Program
int main()
{
int a[Row][Col] = { 2, 2, 3, 3, 4, 4,
5, 5, 7, 7, 7, 4,
1, 2, 7, 7, 7, 4,
4, 4, 7, 7, 7, 4,
5, 5, 5, 1, 2, 7,
8, 7, 9, 4, 4, 4
};
cout << largestKSubmatrix(a) << endl;
return 0;
}
Java
// Java program to find maximum
// K such that K x K is a
// submatrix with equal elements.
class GFG
{
static int Row = 6, Col = 6;
// Returns size of the largest
// square sub-matrix with
// all same elements.
static int largestKSubmatrix(int [][]a)
{
int [][]dp = new int [Row][Col];
int result = 0;
for (int i = 0 ;
i < Row ; i++)
{
for (int j = 0 ;
j < Col ; j++)
{
// If elements is at top
// row or first column,
// it wont form a square
// matrix's bottom-right
if (i == 0 || j == 0)
dp[i][j] = 1;
else
{
// Check if adjacent
// elements are equal
if (a[i][j] == a[i - 1][j] &&
a[i][j] == a[i][j - 1] &&
a[i][j] == a[i - 1][j - 1])
{
dp[i][j] = (dp[i - 1][j] > dp[i][j - 1] &&
dp[i - 1][j] > dp[i - 1][j - 1] + 1) ?
dp[i - 1][j] :
(dp[i][j - 1] > dp[i - 1][j] &&
dp[i][j - 1] > dp[i - 1][j - 1] + 1) ?
dp[i][j - 1] :
dp[i - 1][j - 1] + 1;
}
// If not equal, then it
// will form a 1x1 submatrix
else dp[i][j] = 1;
}
// Update result at each (i,j)
result = result > dp[i][j] ?
result : dp[i][j];
}
}
return result;
}
// Driver code
public static void main(String[] args)
{
int [][]a = {{2, 2, 3, 3, 4, 4},
{5, 5, 7, 7, 7, 4},
{1, 2, 7, 7, 7, 4},
{4, 4, 7, 7, 7, 4},
{5, 5, 5, 1, 2, 7},
{8, 7, 9, 4, 4, 4}};
System.out.println(largestKSubmatrix(a));
}
}
// This code is contributed
// by ChitraNayal
C#
// C# program to find maximum
// K such that K x K is a
// submatrix with equal elements.
using System;
class GFG
{
static int Row = 6, Col = 6;
// Returns size of the
// largest square sub-matrix
// with all same elements.
static int largestKSubmatrix(int[,] a)
{
int[,] dp = new int [Row, Col];
int result = 0;
for (int i = 0 ; i < Row ; i++)
{
for (int j = 0 ;
j < Col ; j++)
{
// If elements is at top
// row or first column,
// it wont form a square
// matrix's bottom-right
if (i == 0 || j == 0)
dp[i, j] = 1;
else
{
// Check if adjacent
// elements are equal
if (a[i, j] == a[i - 1, j] &&
a[i, j] == a[i, j - 1] &&
a[i, j] == a[i - 1, j - 1])
{
dp[i, j] = (dp[i - 1, j] > dp[i, j - 1] &&
dp[i - 1, j] > dp[i - 1, j - 1] + 1) ?
dp[i - 1, j] :
(dp[i, j - 1] > dp[i - 1, j] &&
dp[i, j - 1] > dp[i - 1, j - 1] + 1) ?
dp[i, j - 1] :
dp[i - 1, j - 1] + 1;
}
// If not equal, then
// it will form a 1x1
// submatrix
else dp[i, j] = 1;
}
// Update result at each (i,j)
result = result > dp[i, j] ?
result : dp[i, j];
}
}
return result;
}
// Driver Code
public static void Main()
{
int[,] a = {{2, 2, 3, 3, 4, 4},
{5, 5, 7, 7, 7, 4},
{1, 2, 7, 7, 7, 4},
{4, 4, 7, 7, 7, 4},
{5, 5, 5, 1, 2, 7},
{8, 7, 9, 4, 4, 4}};
Console.Write(largestKSubmatrix(a));
}
}
// This code is contributed
// by ChitraNayal
Python 3
# Python 3 program to find # maximum K such that K x K # is a submatrix with equal # elements. Row = 6 Col = 6 # Returns size of the # largest square sub-matrix # with all same elements. def largestKSubmatrix(a): dp = [[0 for x in range(Row)] for y in range(Col)] result = 0 for i in range(Row ): for j in range(Col): # If elements is at top # row or first column, # it wont form a square # matrix's bottom-right if (i == 0 or j == 0): dp[i][j] = 1 else: # Check if adjacent # elements are equal if (a[i][j] == a[i - 1][j] and a[i][j] == a[i][j - 1] and a[i][j] == a[i - 1][j - 1]): dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1] ) + 1 # If not equal, then # it will form a 1x1 # submatrix else: dp[i][j] = 1 # Update result at each (i,j) result = max(result, dp[i][j]) return result # Driver Code a = [[ 2, 2, 3, 3, 4, 4], [ 5, 5, 7, 7, 7, 4], [ 1, 2, 7, 7, 7, 4], [ 4, 4, 7, 7, 7, 4], [ 5, 5, 5, 1, 2, 7], [ 8, 7, 9, 4, 4, 4]]; print(largestKSubmatrix(a)) # This code is contributed # by ChitraNayal
PHP
<?php
// Java program to find maximum
// K such that K x K is a
// submatrix with equal elements.
$Row = 6;
$Col = 6;
// Returns size of the largest
// square sub-matrix with
// all same elements.
function largestKSubmatrix(&$a)
{
global $Row, $Col;
$result = 0;
for ($i = 0 ;
$i < $Row ; $i++)
{
for ($j = 0 ;
$j < $Col ; $j++)
{
// If elements is at
// top row or first
// column, it wont form
// a square matrix's
// bottom-right
if ($i == 0 || $j == 0)
$dp[$i][$j] = 1;
else
{
// Check if adjacent
// elements are equal
if ($a[$i][$j] == $a[$i - 1][$j] &&
$a[$i][$j] == $a[$i][$j - 1] &&
$a[$i][$j] == $a[$i - 1][$j - 1] )
$dp[$i][$j] = min(min($dp[$i - 1][$j],
$dp[$i][$j - 1]),
$dp[$i - 1][$j - 1] ) + 1;
// If not equal, then it
// will form a 1x1 submatrix
else $dp[$i][$j] = 1;
}
// Update result at each (i,j)
$result = max($result,
$dp[$i][$j]);
}
}
return $result;
}
// Driver Code
$a = array(array(2, 2, 3, 3, 4, 4),
array(5, 5, 7, 7, 7, 4),
array(1, 2, 7, 7, 7, 4),
array(4, 4, 7, 7, 7, 4),
array(5, 5, 5, 1, 2, 7),
array(8, 7, 9, 4, 4, 4));
echo largestKSubmatrix($a);
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// Javascript program to find maximum
// K such that K x K is a
// submatrix with equal elements.
let Row = 6, Col = 6;
// Returns size of the largest
// square sub-matrix with
// all same elements.
function largestKSubmatrix(a)
{
let dp = new Array(Row);
for(let i = 0; i < Row; i++)
{
dp[i] = new Array(Col);
for(let j = 0; j < Col; j++)
{
dp[i][j] = 0;
}
}
let result = 0;
for (let i = 0 ;
i < Row ; i++)
{
for (let j = 0 ;
j < Col ; j++)
{
// If elements is at top
// row or first column,
// it wont form a square
// matrix's bottom-right
if (i == 0 || j == 0)
dp[i][j] = 1;
else
{
// Check if adjacent
// elements are equal
if (a[i][j] == a[i - 1][j] &&
a[i][j] == a[i][j - 1] &&
a[i][j] == a[i - 1][j - 1])
{
dp[i][j] = (dp[i - 1][j] > dp[i][j - 1] &&
dp[i - 1][j] > dp[i - 1][j - 1] + 1) ?
dp[i - 1][j] :
(dp[i][j - 1] > dp[i - 1][j] &&
dp[i][j - 1] > dp[i - 1][j - 1] + 1) ?
dp[i][j - 1] :
dp[i - 1][j - 1] + 1;
}
// If not equal, then it
// will form a 1x1 submatrix
else dp[i][j] = 1;
}
// Update result at each (i,j)
result = result > dp[i][j] ?
result : dp[i][j];
}
}
return result;
}
// Driver code
let a = [[ 2, 2, 3, 3, 4, 4],
[ 5, 5, 7, 7, 7, 4],
[ 1, 2, 7, 7, 7, 4],
[ 4, 4, 7, 7, 7, 4],
[ 5, 5, 5, 1, 2, 7],
[ 8, 7, 9, 4, 4, 4]];
document.write(largestKSubmatrix(a));
// This code is contributed by avanitrachhadiya2155
</script>
Producción
3
Complejidad de tiempo: O (fila * columna)
Espacio auxiliar: O (fila * columna)
Este artículo es una contribución de Shubham Gupta . 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.
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