La subarray cuadrada más grande posible con el valor Y máximo

Dada una array de enteros de [ ][ ] dimensiones, la tarea es encontrar la array cuadrada más grande posible a partir de la array dada con el valor AND máximo . 

El valor AND de una array se define como el valor obtenido después de realizar una operación AND bit a bit en todos los elementos de la array. 
 

Ejemplos: 

Entrada: mat [ ][ ] = {{2, 3, 3}, {2, 3, 3}, {2, 2, 2}} 
Salida: 4 
Explicación: 
la subarray cuadrada dada tiene un valor AND de 2. 
La subarray 
{{ 3, 3} 
{3, 3}} 
de tamaño 4 tiene un valor AND máximo de 3. Todas las demás subarrays cuadradas de tamaño 4 tienen un valor AND de 2.

Entrada: mat [ ][ ] = 
{{9, 9, 9, 8}, 
{9, 9, 9, 6}, 
{9, 9, 9, 3}, 
{2, 2, 2, 2}} 
Salida : 9 
Explicación: 
La subarray de tamaño 9 
{{9, 9, 9}, 
{9, 9, 9}, 
{9, 9, 9}} 
tiene un valor AND máximo de 9. 
 

Enfoque ingenuo: 
genera todas las subarrays cuadradas a partir de la array dada. Inicialice una respuesta variable para almacenar el valor & máximo de las subarrays y otra variable count para almacenar el número de elementos en la subarray. Imprime el valor máximo de conteo correspondiente a la respuesta de valor Y máxima obtenida de todas las subarrays cuadradas.

Enfoque eficiente: 
siga los pasos a continuación para optimizar la solución anterior: 

• Para maximizar el valor de &, necesitamos encontrar una subarray que consista solo en el elemento máximo en la array. Esto se debe a que el valor AND máximo posible en la array es el elemento máximo presente en la array.
• Encuentre el valor máximo posible presente en la array.
• Utilice el enfoque de programación dinámica para obtener la subarray de tamaño máximo llena solo con el elemento de array máximo.
• Cree un dp[][] auxiliar tal que dp[i][j] almacene la subarray cuadrada más grande posible de la que mat[i][j] pueda ser parte tal que el valor AND de esa subarray sea igual a mat[i] [j].
• La relación de recurrencia es la siguiente:

Si mat[i][j] es igual a {mat[i-1][j], mat[i][j-1], mat[i-1][j-1]} entonces considere los tres valores como una subarray cuadrada y actualice DP[i][j] como: 
DP[i][j] = min(DP[i-1][j], DP[i][j-1], DP[i-1 ][j-1]) + 1 
De lo contrario, 
DP[i][j] = 1 
La respuesta sería el máximo de todos los DP [i][j] 
 

• Finalmente, itere sobre la array dp[][] y encuentre el dp[i][j] más grande para cada mat[i][j] igual al elemento máximo en la array.

A continuación se muestra la implementación del enfoque anterior:  

// C++ program to find
// the length of longest
// possible square submatrix
// with maximum AND value
// from the given matrix
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate and
// return the length of
// square submatrix with
// maximum AND value
int MAX_value(vector<vector<int> > arr)
{
    // Extract dimensions
    int row = arr.size();
    int col = arr[0].size();
 
    // Auxiliary array
    int dp[row][col];
 
    // Initialize auxiliary array
    memset(dp, sizeof(dp), 0);
 
    // c: Stores the maximum
    // value in the matrix
    // p: Stores the number
    // of elements in the
    // submatrix having
    // maximum AND value
    int i = 0, j = 0;
    int c = arr[0][0], p = 0;
    int d = row;
 
    // Iterate over the matrix
    // to fill the auxiliary
    // matrix
    for (i = 0; i < d; i++) {
        for (j = 0; j < d; j++) {
 
            // Find the max element in the
            // matrix side by side
            if (c < arr[i][j]) {
                c = arr[i][j];
            }
 
            // Fill first row and
            // column with 1's
            if (i == 0 || j == 0) {
                dp[i][j] = 1;
            }
            else {
 
                // For every cell, check if
                // the elements at the left,
                // top and top left cells
                // from the current cell
                // are equal or not
                if (arr[i - 1][j - 1] == arr[i][j]
                    && arr[i - 1][j] == arr[i][j]
                    && arr[i][j - 1] == arr[i][j]) {
 
                    // Store the minimum possible
                    // submatrix size these
                    // elements are part of
                    dp[i][j]
                        = min(dp[i - 1][j - 1],
                            min(dp[i - 1][j],
                                dp[i][j - 1]))
                        + 1;
                }
                else {
                    // Store 1 otherwise
                    dp[i][j] = 1;
                }
            }
        }
    }
 
    for (i = 0; i < d; i++) {
        for (j = 0; j < d; j++) {
 
            // checking maximum value
            if (arr[i][j] == c) {
 
                // If the maximum AND
                // value occurs more
                // than once
                if (p < dp[i][j]) {
 
                    // Update the maximum
                    // size of submatrix
                    p = dp[i][j];
                }
            }
        }
    }
    // final output
    return p * p;
}
 
// Driver Program
int main()
{
    vector<vector<int> > arr
        = { { 9, 9, 3, 3, 4, 4 },
            { 9, 9, 7, 7, 7, 4 },
            { 1, 2, 7, 7, 7, 4 },
            { 4, 4, 7, 7, 7, 4 },
            { 5, 5, 1, 1, 2, 7 },
            { 2, 7, 1, 1, 4, 4 } };
 
    cout << MAX_value(arr) << endl;
 
    return 0;
}

// Java program to find the length
// of longest possible square
// submatrix with maximum AND
// value from the given matrix
import java.util.*;
 
class GFG{
 
// Function to calculate and return
// the length of square submatrix
// with maximum AND value
static int MAX_value(int [][]arr)
{
     
    // Extract dimensions
    int row = arr.length;
    int col = arr[0].length;
 
    // Auxiliary array
    int [][]dp = new int[row][col];
 
    // c: Stores the maximum
    // value in the matrix
    // p: Stores the number
    // of elements in the
    // submatrix having
    // maximum AND value
    int i = 0, j = 0;
    int c = arr[0][0], p = 0;
    int d = row;
 
    // Iterate over the matrix
    // to fill the auxiliary
    // matrix
    for(i = 0; i < d; i++)
    {
        for(j = 0; j < d; j++)
        {
             
            // Find the max element in
            // the matrix side by side
            if (c < arr[i][j])
            {
                c = arr[i][j];
            }
 
            // Fill first row and
            // column with 1's
            if (i == 0 || j == 0)
            {
                dp[i][j] = 1;
            }
            else
            {
 
                // For every cell, check if the
                // elements at the left, top and
                // top left cells from the current
                // cell are equal or not
                if (arr[i - 1][j - 1] == arr[i][j] &&
                    arr[i - 1][j] == arr[i][j] &&
                    arr[i][j - 1] == arr[i][j])
                {
                     
                    // Store the minimum possible
                    // submatrix size these
                    // elements are part of
                    dp[i][j] = Math.min(dp[i - 1][j - 1],
                               Math.min(dp[i - 1][j],
                                        dp[i][j - 1])) + 1;
                }
                else
                {
                     
                    // Store 1 otherwise
                    dp[i][j] = 1;
                }
            }
        }
    }
    for(i = 0; i < d; i++)
    {
        for(j = 0; j < d; j++)
        {
             
            // Checking maximum value
            if (arr[i][j] == c)
            {
                 
                // If the maximum AND
                // value occurs more
                // than once
                if (p < dp[i][j])
                {
                     
                    // Update the maximum
                    // size of submatrix
                    p = dp[i][j];
                }
            }
        }
    }
     
    // Final output
    return p * p;
}
 
// Driver code
public static void main(String[] args)
{
    int [][]arr = { { 9, 9, 3, 3, 4, 4 },
                    { 9, 9, 7, 7, 7, 4 },
                    { 1, 2, 7, 7, 7, 4 },
                    { 4, 4, 7, 7, 7, 4 },
                    { 5, 5, 1, 1, 2, 7 },
                    { 2, 7, 1, 1, 4, 4 } };
 
    System.out.print(MAX_value(arr) + "\n");
}
}
 
// This code contributed by amal kumar choubey

# Python3 program to find the length
# of longest possible square submatrix
# with maximum AND value from the given
# matrix
 
# Function to calculate and return the
# length of square submatrix with
# maximum AND value
def MAX_value(arr):
     
    # Extract dimensions
    row = len(arr)
    col = len(arr)
 
    # Auxiliary array
    # Initialize auxiliary array
    dp = [[0 for i in range(col)]
             for j in range(row)]
 
    # c: Stores the maximum
    # value in the matrix
    # p: Stores the number
    # of elements in the
    # submatrix having
    # maximum AND value
    i, j = 0, 0
    c, p = arr[0][0], 0
    d = row
 
    # Iterate over the matrix
    # to fill the auxiliary
    # matrix
    for i in range(d):
        for j in range(d):
 
            # Find the max element in the
            # matrix side by side
            if (c < arr[i][j]):
                c = arr[i][j]
 
            # Fill first row and
            # column with 1's
            if (i == 0 or j == 0):
                dp[i][j] = 1
            else:
 
                # For every cell, check if
                # the elements at the left,
                # top and top left cells
                # from the current cell
                # are equal or not
                if (arr[i - 1][j - 1] == arr[i][j] and
                    arr[i - 1][j] == arr[i][j] and
                    arr[i][j - 1] == arr[i][j]):
 
                    # Store the minimum possible
                    # submatrix size these
                    # elements are part of
                    dp[i][j] = min(dp[i - 1][j - 1],
                               min(dp[i - 1][j],
                                dp[i][j - 1])) + 1
                else:
                     
                    # Store 1 otherwise
                    dp[i][j] = 1
 
    for i in range(d):
        for j in range(d):
 
            # Checking maximum value
            if (arr[i][j] == c):
 
                # If the maximum AND
                # value occurs more
                # than once
                if (p < dp[i][j]):
 
                    # Update the maximum
                    # size of submatrix
                    p = dp[i][j]
     
    # Final output
    return p * p
 
# Driver Code
arr = [ [ 9, 9, 3, 3, 4, 4 ],
        [ 9, 9, 7, 7, 7, 4 ],
        [ 1, 2, 7, 7, 7, 4 ],
        [ 4, 4, 7, 7, 7, 4 ],
        [ 5, 5, 1, 1, 2, 7 ],
        [ 2, 7, 1, 1, 4, 4 ]]
 
print(MAX_value(arr))
 
# This code is contributed by divyeshrabadiya07

// C# program to find the length
// of longest possible square
// submatrix with maximum AND
// value from the given matrix
using System;
 
class GFG{
 
// Function to calculate and return
// the length of square submatrix
// with maximum AND value
static int MAX_value(int [,]arr)
{
     
    // Extract dimensions
    int row = arr.GetLength(0);
    int col = arr.GetLength(1);
 
    // Auxiliary array
    int [,]dp = new int[row, col];
 
    // c: Stores the maximum
    // value in the matrix
    // p: Stores the number
    // of elements in the
    // submatrix having
    // maximum AND value
    int i = 0, j = 0;
    int c = arr[0, 0], p = 0;
    int d = row;
 
    // Iterate over the matrix
    // to fill the auxiliary
    // matrix
    for(i = 0; i < d; i++)
    {
        for(j = 0; j < d; j++)
        {
             
            // Find the max element in
            // the matrix side by side
            if (c < arr[i, j])
            {
                c = arr[i, j];
            }
 
            // Fill first row and
            // column with 1's
            if (i == 0 || j == 0)
            {
                dp[i, j] = 1;
            }
            else
            {
                 
                // For every cell, check if the
                // elements at the left, top and
                // top left cells from the current
                // cell are equal or not
                if (arr[i - 1, j - 1] == arr[i, j] &&
                    arr[i - 1, j] == arr[i, j] &&
                    arr[i, j - 1] == arr[i, j])
                {
                     
                    // Store the minimum possible
                    // submatrix size these
                    // elements are part of
                    dp[i, j] = Math.Min(dp[i - 1, j - 1],
                               Math.Min(dp[i - 1, j],
                                        dp[i, j - 1])) + 1;
                }
                else
                {
                     
                    // Store 1 otherwise
                    dp[i, j] = 1;
                }
            }
        }
    }
    for(i = 0; i < d; i++)
    {
        for(j = 0; j < d; j++)
        {
             
            // Checking maximum value
            if (arr[i, j] == c)
            {
                 
                // If the maximum AND
                // value occurs more
                // than once
                if (p < dp[i, j])
                {
                     
                    // Update the maximum
                    // size of submatrix
                    p = dp[i, j];
                }
            }
        }
    }
     
    // Final output
    return p * p;
}
 
// Driver code
public static void Main(String[] args)
{
    int [,]arr = { { 9, 9, 3, 3, 4, 4 },
                   { 9, 9, 7, 7, 7, 4 },
                   { 1, 2, 7, 7, 7, 4 },
                   { 4, 4, 7, 7, 7, 4 },
                   { 5, 5, 1, 1, 2, 7 },
                   { 2, 7, 1, 1, 4, 4 } };
 
    Console.Write(MAX_value(arr) + "\n");
}
}
 
// This code is contributed by gauravrajput1

<script>
 
// Javascript program to find the length
// of longest possible square
// submatrix with maximum AND
// value from the given matrix
 
    // Function to calculate and return
    // the length of square submatrix
    // with maximum AND value
    function MAX_value(arr) {
 
        // Extract dimensions
        var row = arr.length;
        var col = arr[0].length;
 
        // Auxiliary array
        var dp = Array(row);
        for(var i = 0;i<row;i++)
        dp[i] = Array(col).fill(0);
 
        // c: Stores the maximum
        // value in the matrix
        // p: Stores the number
        // of elements in the
        // submatrix having
        // maximum AND value
        var i = 0, j = 0;
        var c = arr[0][0], p = 0;
        var d = row;
 
        // Iterate over the matrix
        // to fill the auxiliary
        // matrix
        for (i = 0; i < d; i++) {
            for (j = 0; j < d; j++) {
 
                // Find the max element in
                // the matrix side by side
                if (c < arr[i][j]) {
                    c = arr[i][j];
                }
 
                // Fill first row and
                // column with 1's
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
 
                    // For every cell, check if the
                    // elements at the left, top and
                    // top left cells from the current
                    // cell are equal or not
                    if (arr[i - 1][j - 1] == arr[i][j] &&
                    arr[i - 1][j] == arr[i][j] &&
                    arr[i][j - 1] == arr[i][j]) {
 
                        // Store the minimum possible
                        // submatrix size these
                        // elements are part of
                        dp[i][j] = Math.min(dp[i - 1][j - 1],
                        Math.min(dp[i - 1][j],
                        dp[i][j - 1])) + 1;
                    } else {
 
                        // Store 1 otherwise
                        dp[i][j] = 1;
                    }
                }
            }
        }
        for (i = 0; i < d; i++) {
            for (j = 0; j < d; j++) {
 
                // Checking maximum value
                if (arr[i][j] == c) {
 
                    // If the maximum AND
                    // value occurs more
                    // than once
                    if (p < dp[i][j]) {
 
                        // Update the maximum
                        // size of submatrix
                        p = dp[i][j];
                    }
                }
            }
        }
 
        // Final output
        return p * p;
    }
 
    // Driver code
     
        var arr = [ [ 9, 9, 3, 3, 4, 4 ],
                    [ 9, 9, 7, 7, 7, 4 ],
                    [ 1, 2, 7, 7, 7, 4 ],
                    [ 4, 4, 7, 7, 7, 4 ],
                    [ 5, 5, 1, 1, 2, 7 ],
                    [ 2, 7, 1, 1, 4, 4 ] ];
 
        document.write(MAX_value(arr) + "\n");
 
// This code contributed by umadevi9616
 
</script>

4

Complejidad de tiempo : O (N * N), ya que estamos usando bucles anidados para atravesar N * N veces.

Espacio auxiliar : O(N*N), ya que estamos usando espacio adicional para la array.