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