Área máxima de subarray que tiene un recuento de 1 uno más que un recuento de 0

Dada una array binaria N x N. El problema es encontrar la subarray de área máxima que tenga una cuenta de 1 más que una cuenta de 0.
Ejemplos: 

Input : mat[][] = { {1, 0, 0, 1},
                    {0, 1, 1, 1},
                    {1, 0, 0, 0},
                    {0, 1, 0, 1} }
Output : 9
The sub-matrix defined by the boundary values (1, 1) and (3, 3).
{ {1, 0, 0, 1},
  {0, 1, 1, 1},
  {1, 0, 0, 0},
  {0, 1, 0, 1} }

Enfoque ingenuo: verifique todos los rectángulos posibles en una array 2D dada. Esta solución requiere 4 bucles anidados y la complejidad temporal de esta solución sería O(n^4).

Enfoque eficiente: un enfoque eficiente será usar el subarreglo más largo que tenga un recuento de 1 más que un recuento de 0 , lo que reduce la complejidad del tiempo a O (n ^ 3). La idea es arreglar las columnas izquierda y derecha una por una y encontrar la longitud máxima de filas contiguas que tengan el recuento de 1 uno más que el recuento de 0 para cada par de columnas izquierda y derecha. Encuentre los números de las filas superior e inferior (que tienen una longitud máxima) para cada par de columnas fijas izquierda y derecha. Para encontrar los números de las filas superior e inferior, calcule la suma de los elementos en cada fila de izquierda a derecha y almacene estas sumas en una array, digamos temp[] (considere 0 como -1 al agregarlo). Entonces temp[i] indica la suma de los elementos de izquierda a derecha en la fila i. Utilizando el enfoque enEl subarreglo más largo que tiene un conteo de 1 uno más que un conteo de 0 , la array temp[] se usa para obtener el subarreglo de longitud máxima de temp[] con un conteo de 1 uno más que un conteo de 0 al obtener los números de fila inicial y final, luego estos valores se pueden usar para encontrar el área máxima posible con la izquierda y la derecha como columnas de límite. Para obtener el área máxima general, compare esta área con el área máxima hasta ahora. 

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

C++

// C++ implementation to find
// the maximum area sub-matrix
// having count of 1's
// one more than count of 0's
#include <bits/stdc++.h>
 
using namespace std;
 
#define SIZE 10
 
// function to find the length of longest
// subarray having count of 1's one more
// than count of 0's
int lenOfLongSubarr(int arr[], int n,
                    int& start, int& finish)
{
    // unordered_map 'um' implemented as
    // hash table
    unordered_map<int, int> um;
    int sum = 0, maxLen = 0;
 
    // traverse the given array
    for (int i = 0; i < n; i++) {
 
        // accumulating sum
        sum += arr[i];
 
        // when subarray starts form index '0'
        if (sum == 1) {
            start = 0;
            finish = i;
            maxLen = i + 1;
        }
 
        // make an entry for 'sum' if it is
        // not present in 'um'
        else if (um.find(sum) == um.end())
            um[sum] = i;
 
        // check if 'sum-1' is present in 'um'
        // or not
        if (um.find(sum - 1) != um.end()) {
 
            // update 'start', 'finish'
            // and maxLength
            if (maxLen < (i - um[sum - 1]))
                start = um[sum - 1] + 1;
            finish = i;
            maxLen = i - um[sum - 1];
        }
    }
 
    // required maximum length
    return maxLen;
}
 
// function to find the maximum
// area sub-matrix having
// count of 1's one more than count of 0's
void largestSubmatrix(int mat[SIZE][SIZE], int n)
{
    // variables to store final
    // and intermediate results
    int finalLeft, finalRight, finalTop, finalBottom;
    int temp[n], maxArea = 0, len, start, finish;
 
    // set the left column
    for (int left = 0; left < n; left++) {
 
        // Initialize all elements of temp as 0
        memset(temp, 0, sizeof(temp));
 
        // Set the right column for the
        // left column set by outer loop
        for (int right = left; right < n; right++) {
 
            // Calculate sum between current left and right
            // for every row 'i', consider '0' as '-1'
            for (int i = 0; i < n; ++i)
                temp[i] += mat[i][right] == 0 ? -1 : 1;
 
            // function to set the 'start' and 'finish'
            // variables having index values of
            // temp[] which contains the longest
            // subarray of temp[] having count of 1's
            // one more than count of 0's
            len = lenOfLongSubarr(temp, n, start, finish);
 
            // Compare with maximum area
            // so far and accordingly update the
            // final variables
            if ((len != 0) && (maxArea < (finish - start + 1)
                                             * (right - left + 1))) {
                finalLeft = left;
                finalRight = right;
                finalTop = start;
                finalBottom = finish;
                maxArea = (finish - start + 1) * (right - left + 1);
            }
        }
    }
 
    // Print final values
    cout << "(Top, Left): (" << finalTop << ", "
         << finalLeft << ")\n";
 
    cout << "(Bottom, Right): (" << finalBottom << ", "
         << finalRight << ")\n";
 
    cout << "Maximum area: " << maxArea;
}
 
// Driver Code
int main()
{
    int mat[SIZE][SIZE] = { { 1, 0, 0, 1 },
                            { 0, 1, 1, 1 },
                            { 1, 0, 0, 0 },
                            { 0, 1, 0, 1 } };
    int n = 4;
    largestSubmatrix(mat, n);
    return 0;
}

Java

// Java implementation to find
// the maximum area sub-matrix
// having count of 1's
// one more than count of 0's
import java.util.*;
 
class GFG
{
 
static int start, finish;
 
// Function to find the length of longest
// subarray having count of 1's one more
// than count of 0's
static int lenOfLongSubarr(int []arr, int n)
{
     
    // unordered_map 'um' implemented as
    // hash table
    HashMap<Integer,Integer> um = new HashMap<Integer, Integer>();
     
    int sum = 0, maxLen = 0;
 
    // Traverse the given array
    for(int i = 0; i < n; i++)
    {
         
        // Accumulating sum
        sum += arr[i];
 
        // When subarray starts form index '0'
        if (sum == 1)
        {
            start = 0;
            finish = i;
            maxLen = i + 1;
        }
 
        // Make an entry for 'sum' if it is
        // not present in 'um'
        else if (!um.containsKey(sum))
            um.put(sum,i);
 
        // Check if 'sum-1' is present in 'um'
        // or not
        if (um.containsKey(sum - 1))
        {
             
            // Update 'start', 'finish'
            // and maxLength
            if (maxLen < (i - um.get(sum - 1)))
                start = um.get(sum - 1) + 1;
                 
            finish = i;
            maxLen = i - um.get(sum - 1);
        }
    }
     
    // Required maximum length
    return maxLen;
}
 
// Function to find the maximum
// area sub-matrix having
// count of 1's one more than count of 0's
static void largestSubmatrix(int [][]mat, int n)
{
     
    // Variables to store final
    // and intermediate results
    int finalLeft = 0, finalRight = 0,
        finalTop = 0, finalBottom = 0;
    int maxArea = 0, len;
    finish = 0;
    start=0;
     
    int []temp = new int[n];
     
    // Set the left column
    for(int left = 0; left < n; left++)
    {
         
        // Initialize all elements of temp as 0
        Arrays.fill(temp, 0);
 
        // Set the right column for the
        // left column set by outer loop
        for(int right = left; right < n; right++)
        {
             
            // Calculate sum between current left
            // and right for every row 'i',
            // consider '0' as '-1'
            for(int i = 0; i < n; ++i)
                temp[i] += mat[i][right] == 0 ? -1 : 1;
 
            // Function to set the 'start' and 'finish'
            // variables having index values of
            // temp[] which contains the longest
            // subarray of temp[] having count of 1's
            // one more than count of 0's
            len = lenOfLongSubarr(temp, n);
 
            // Compare with maximum area
            // so far and accordingly update the
            // final variables
            if ((len != 0) &&
                (maxArea < (finish - start + 1) *
                            (right - left + 1)))
            {
                finalLeft = left;
                finalRight = right;
                finalTop = start;
                finalBottom = finish;
                maxArea = (finish - start + 1) *
                            (right - left + 1);
            }
        }
    }
 
    // Print final values
    System.out.print("(Top, Left): (" + finalTop +
                ", " + finalLeft + ")\n");
     
    System.out.print("(Bottom, Right): (" + finalBottom +
                    ", " + finalRight + ")\n");
     
    System.out.print("Maximum area: " + maxArea);
 
}
 
// Driver code
public static void main(String[] args)
{
    int [][]mat = new int[][]{ { 1, 0, 0, 1 },
                            { 0, 1, 1, 1 },
                            { 1, 0, 0, 0 },
                            { 0, 1, 0, 1 } };
    int n = 4;
     
    largestSubmatrix(mat, n);
}
}
 
// This code is contributed by pratham76

Python3

# Python implementation to find
# the maximum area sub-matrix
# having count of 1's
# one more than count of 0's
 
# function to find the length of longest
# subarray having count of 1's one more
# than count of 0's
def lenOfLongSubarr(arr, n, start, finish):
   
  # unordered_map 'um' implemented as
  # hash table
  um = {}
  sum = 0
  maxLen = 0
   
  # traverse the given array
  for i in range(n):
     
    # accumulating sum
    sum += arr[i]
     
    # when subarray starts form index '0'
    if (sum == 1):
      start = 0
      finish = i
      maxLen = i + 1
       
    # make an entry for 'sum' if it is
    # not present in 'um'
    elif (sum not in um):
      um[sum] = i
       
    # check if 'sum-1' is present in 'um'
    # or not
    if (sum - 1 in um):
       
      # update 'start', 'finish'
      # and maxLength
      if (maxLen < (i - um[sum - 1])):
        start = um[sum - 1] + 1
        finish = i
        maxLen = i - um[sum - 1]
 
  # required maximum length
  return [maxLen,start,finish]
 
# function to find the maximum
# area sub-matrix having
# count of 1's one more than count of 0's
def largestSubmatrix(mat, n):
   
  # variables to store final
  # and intermediate results
  temp = []
  maxArea = 0
   
  # set the left column
  for left in range(n):
     
    # Initialize all elements of temp as 0
    temp = [0 for i in range(n)]
     
    # Set the right column for the
    # left column set by outer loop
    for right in range(left, n):
       
      # Calculate sum between current left and right
      # for every row 'i', consider '0' as '-1'
      for i in range(n):
        if mat[i][right] == 0:
          temp[i] -= 1
        else:
          temp[i] += 1
 
      # function to set the 'start' and 'finish'
      # variables having index values of
      # temp[] which contains the longest
      # subarray of temp[] having count of 1's
      # one more than count of 0's
      start = 0
      finish = 0
      fc = lenOfLongSubarr(temp, n, start, finish)
      len = fc[0]
      start = fc[1]
      finish = fc[2]
       
      # Compare with maximum area
      # so far and accordingly update the
      # final variables
      if ((len != 0) and (maxArea < (finish - start + 1) * (right - left + 1))):
        finalLeft = left
        finalRight = right
        finalTop = start
        finalBottom = finish
        maxArea = (finish - start + 1) * (right - left + 1)
 
  # Print final values
  print("(Top, Left): (",finalTop,", ",finalLeft,")")
  print("(Bottom, Right): (",finalBottom, ", ",finalRight,")")
  print("Maximum area: ", maxArea)
 
# Driver Code
mat = [[1, 0, 0, 1 ], [ 0, 1, 1, 1 ], [ 1, 0, 0, 0 ], [ 0, 1, 0, 1 ]]
n = 4
largestSubmatrix(mat, n)
 
# This code is contributed by rohitsingh07052

C#

// C# implementation to find
// the maximum area sub-matrix
// having count of 1's
// one more than count of 0's
using System;
using System.Collections.Generic;
using System.Collections;
 
class GFG{
 
// Function to find the length of longest
// subarray having count of 1's one more
// than count of 0's
static int lenOfLongSubarr(int []arr, int n,
                       ref int start, ref int finish)
{
     
    // unordered_map 'um' implemented as
    // hash table
    Dictionary<int,
               int> um = new Dictionary<int,
                                        int>();
     
    int sum = 0, maxLen = 0;
  
    // Traverse the given array
    for(int i = 0; i < n; i++)
    {
         
        // Accumulating sum
        sum += arr[i];
  
        // When subarray starts form index '0'
        if (sum == 1)
        {
            start = 0;
            finish = i;
            maxLen = i + 1;
        }
  
        // Make an entry for 'sum' if it is
        // not present in 'um'
        else if (!um.ContainsKey(sum))
            um[sum] = i;
  
        // Check if 'sum-1' is present in 'um'
        // or not
        if (um.ContainsKey(sum - 1))
        {
             
            // Update 'start', 'finish'
            // and maxLength
            if (maxLen < (i - um[sum - 1]))
                start = um[sum - 1] + 1;
                 
            finish = i;
            maxLen = i - um[sum - 1];
        }
    }
     
    // Required maximum length
    return maxLen;
}
  
// Function to find the maximum
// area sub-matrix having
// count of 1's one more than count of 0's
static void largestSubmatrix(int [,]mat, int n)
{
     
    // Variables to store final
    // and intermediate results
    int finalLeft = 0, finalRight = 0,
         finalTop = 0, finalBottom = 0;
    int maxArea = 0, len, start = 0, finish = 0;
     
    int []temp = new int[n];
     
    // Set the left column
    for(int left = 0; left < n; left++)
    {
         
        // Initialize all elements of temp as 0
        Array.Fill(temp, 0);
  
        // Set the right column for the
        // left column set by outer loop
        for(int right = left; right < n; right++)
        {
             
            // Calculate sum between current left
            // and right for every row 'i',
            // consider '0' as '-1'
            for(int i = 0; i < n; ++i)
                temp[i] += mat[i, right] == 0 ? -1 : 1;
  
            // Function to set the 'start' and 'finish'
            // variables having index values of
            // temp[] which contains the longest
            // subarray of temp[] having count of 1's
            // one more than count of 0's
            len = lenOfLongSubarr(temp, n, ref start,
                                           ref finish);
  
            // Compare with maximum area
            // so far and accordingly update the
            // final variables
            if ((len != 0) &&
                (maxArea < (finish - start + 1) *
                             (right - left + 1)))
            {
                finalLeft = left;
                finalRight = right;
                finalTop = start;
                finalBottom = finish;
                maxArea = (finish - start + 1) *
                            (right - left + 1);
            }
        }
    }
  
    // Print final values
    Console.Write("(Top, Left): (" + finalTop +
                  ", " + finalLeft + ")\n");
     
    Console.Write("(Bottom, Right): (" + finalBottom +
                     ", " + finalRight + ")\n");
     
    Console.Write("Maximum area: " + maxArea);
  
}
 
// Driver code
public static void Main(string[] args)
{
    int [,]mat = new int[,]{ { 1, 0, 0, 1 },
                             { 0, 1, 1, 1 },
                             { 1, 0, 0, 0 },
                             { 0, 1, 0, 1 } };
    int n = 4;
     
    largestSubmatrix(mat, n);
}
}
 
// This code is contributed by rutvik_56

Javascript

<script>
 
// JavaScript implementation to find
// the maximum area sub-matrix
// having count of 1's
// one more than count of 0's
 
// function to find the length of longest
// subarray having count of 1's one more
// than count of 0's
function lenOfLongSubarr(arr, n, start, finish){
   
  // unordered_map 'um' implemented as
  // hash table
  let um = new Map()
  let sum = 0
  let maxLen = 0
   
  // traverse the given array
  for(let i=0;i<n;i++){
     
    // accumulating sum
    sum += arr[i]
     
    // when subarray starts form index '0'
    if (sum == 1){
      start = 0
      finish = i
      maxLen = i + 1
    }
       
    // make an entry for 'sum' if it is
    // not present in 'um'
    else if (um.has(sum) == false)
      um.set(sum,i)
       
    // check if 'sum-1' is present in 'um'
    // or not
    if (um.has(sum - 1)){
       
      // update 'start', 'finish'
      // and maxLength
      if (maxLen < (i - um.get(sum - 1))){
        start = um.get(sum - 1) + 1
        finish = i
        maxLen = i - um.get(sum - 1)
      }
    }
  }
 
  // required maximum length
  return [maxLen,start,finish]
}
 
// function to find the maximum
// area sub-matrix having
// count of 1's one more than count of 0's
function largestSubmatrix(mat, n){
   
  // variables to store final
  // and intermediate results
  let temp = []
  let maxArea = 0
   
  let finalLeft,finalRight,finalTop,finalBottom;
 
  // set the left column
  for(let left=0;left<n;left++){
     
    // Initialize all elements of temp as 0
    temp = new Array(n).fill(0)
     
    // Set the right column for the
    // left column set by outer loop
    for(let right = left;right<n;right++){
       
      // Calculate sum between current left and right
      // for every row 'i', consider '0' as '-1'
      for(let i=0;i<n;i++){
        if(mat[i][right] == 0)
          temp[i] -= 1
        else
          temp[i] += 1
      }
 
      // function to set the 'start' and 'finish'
      // variables having index values of
      // temp[] which contains the longest
      // subarray of temp[] having count of 1's
      // one more than count of 0's
      let start = 0
      let finish = 0
      let fc = lenOfLongSubarr(temp, n, start, finish)
      let len = fc[0]
      start = fc[1]
      finish = fc[2]
 
      // Compare with maximum area
      // so far and accordingly update the
      // final variables
      if ((len != 0) && (maxArea < (finish - start + 1) * (right - left + 1))){
        finalLeft = left
        finalRight = right
        finalTop = start
        finalBottom = finish
        maxArea = (finish - start + 1) * (right - left + 1)
      }
    }
  }
 
  // Print final values
  document.write("(Top, Left): (" + finalTop + ", " + finalLeft + ")","</br>")
  document.write("(Bottom, Right): (" + finalBottom  + ", " + finalRight + ")","</br>")
  document.write("Maximum area: "+  maxArea,"</br>")
}
 
// Driver Code
let mat = [[1, 0, 0, 1 ], [ 0, 1, 1, 1 ], [ 1, 0, 0, 0 ], [ 0, 1, 0, 1 ]]
let n = 4
largestSubmatrix(mat, n)
 
// This code is contributed by shinjanpatra
 
</script>
Producción: 

(Top, Left): (1, 1)
(Bottom, Right): (3, 3)
Maximum area: 9

 

Complejidad Temporal: O(N 3 ). 
Espacio Auxiliar: O(N).
 

Publicación traducida automáticamente

Artículo escrito por ayushjauhari14 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 *