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>
(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