Dada una array binaria mat[][] y un entero K , la tarea es encontrar la subarray de tamaño K*K tal que contenga el número máximo de 1 en la array.
Ejemplos:
Entrada: mat[][] = {{1, 0, 1}, {1, 1, 0}, {1, 0, 0}}, K = 2
Salida: 3
Explicación:
En la array dada, hay 4 subarray de orden 2*2,
|1 0| |0 1| |1 1| |1 0|
|1 1|, |1 0|, |1 0|, |0 0|
De estas subarray, dos arrays contienen 3, 1’s.Entrada: mat[][] = {{1, 0}, {0, 1}}, K = 1
Salida: 1
Explicación:
En la array dada, hay 4 subarray de orden 1*1,
|1| , |0|, |1|, |0|
De estas subarray, dos arrays contienen 1, 1’s.
Enfoque: La idea es usar la técnica de la ventana deslizante para resolver este problema. En esta técnica, generalmente calculamos el valor de una ventana y luego deslizamos la ventana una por una para calcular la solución para cada ventana de tamaño K.
Para calcule la subarray máxima de 1, cuente el número de 1 en la fila para cada ventana posible de tamaño K utilizando la técnica de ventana deslizante y almacene los recuentos de 1 en forma de array.
Por ejemplo:
Let the matrix be {{1,0,1}, {1, 1, 0}} and K = 2
For Row 1 -
Subarray 1: (1, 0), Count of 1 = 1
Subarray 2: (0, 1), Count of 1 = 1
For Row 2 -
Subarray 1: (1, 1), Count of 1 = 2
Subarray 2: (1, 0), Count of 1 = 1
Then the final matrix for count of 1's will be -
[ 1, 1 ]
[ 2, 1 ]
De manera similar, aplique la técnica de la ventana deslizante en cada columna de esta array, para calcular el recuento de 1 en cada subarray posible y sacar el máximo de esos recuentos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// maximum count of 1's in
// submatrix of order K
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum
// count of 1's in the
// submatrix of order K
int maxCount(vector<vector<int>> &mat, int k) {
int n = mat.size();
int m = mat[0].size();
vector<vector<int>> a;
// Loop to find the count of 1's
// in every possible windows
// of rows of matrix
for (int e = 0; e < n; ++e){
vector<int> s = mat[e];
vector<int> q;
int c = 0;
// Loop to find the count of
// 1's in the first window
int i;
for (i = 0; i < k; ++i)
if(s[i] == 1)
c += 1;
q.push_back(c);
int p = s[0];
// Loop to find the count of
// 1's in the remaining windows
for (int j = i + 1; j < m; ++j) {
if(s[j] == 1)
c+= 1;
if(p == 1)
c-= 1;
q.push_back(c);
p = s[j-k + 1];
}
a.push_back(q);
}
vector<vector<int>> b;
int max = 0;
// Loop to find the count of 1's
// in every possible submatrix
for (int i = 0; i < a[0].size(); ++i) {
int c = 0;
int p = a[0][i];
// Loop to find the count of
// 1's in the first window
int j;
for (j = 0; j < k; ++j) {
c+= a[j][i];
}
vector<int> q;
if (c>max)
max = c;
q.push_back(c);
// Loop to find the count of
// 1's in the remaining windows
for (int l = j + 1; j < n; ++j) {
c+= a[l][i];
c-= p;
p = a[l-k + 1][i];
q.push_back(c);
if (c > max)
max = c;
}
b.push_back(q);
}
return max;
}
// Driver code
int main()
{
vector<vector<int>> mat = {{1, 0, 1}, {1, 1, 0}, {0, 1, 0}};
int k = 3;
// Function call
cout<< maxCount(mat, k);
return 0;
}
Java
// Java implementation to find the
// maximum count of 1's in
// submatrix of order K
import java.io.*;
import java.util.*;
class GFG{
// Function to find the maximum
// count of 1's in the
// submatrix of order K
static int maxCount(ArrayList<ArrayList<Integer> > mat, int k)
{
int n = mat.size();
int m = mat.get(0).size();
ArrayList<ArrayList<Integer>> a = new ArrayList<ArrayList<Integer>>();
// Loop to find the count of 1's
// in every possible windows
// of rows of matrix
for(int e = 0; e < n; ++e)
{
ArrayList<Integer> s = mat.get(e);
ArrayList<Integer> q = new ArrayList<Integer>();
int c = 0;
// Loop to find the count of
// 1's in the first window
int i;
for(i = 0; i < k; ++i)
{
if (s.get(i) == 1)
{
c += 1;
}
}
q.add(c);
int p = s.get(0);
// Loop to find the count of
// 1's in the remaining windows
for(int j = i + 1; j < m; ++j)
{
if (s.get(j) == 1)
{
c += 1;
}
if (p == 1)
{
c -= 1;
}
q.add(c);
p = s.get(j - k + 1);
}
a.add(q);
}
ArrayList<ArrayList<Integer>> b = new ArrayList<ArrayList<Integer>>();
int max = 0;
// Loop to find the count of 1's
// in every possible submatrix
for(int i = 0; i < a.get(0).size(); ++i)
{
int c = 0;
int p = a.get(0).get(i);
// Loop to find the count of
// 1's in the first window
int j;
for(j = 0; j < k; ++j)
{
c += a.get(j).get(i);
}
ArrayList<Integer> q = new ArrayList<Integer>();
if (c > max)
{
max = c;
}
q.add(c);
// Loop to find the count of
// 1's in the remaining windows
for(int l = j + 1; j < n; ++j)
{
c += a.get(l).get(i);
c -= p;
p = a.get(l - k + 1).get(i);
q.add(c);
if (c > max)
{
max = c;
}
}
b.add(q);
}
return max;
}
// Driver code
public static void main(String[] args)
{
ArrayList<ArrayList<Integer>> mat = new ArrayList<ArrayList<Integer>>();
mat.add(new ArrayList<Integer>(Arrays.asList(1, 0, 1)));
mat.add(new ArrayList<Integer>(Arrays.asList(1, 1, 0)));
mat.add(new ArrayList<Integer>(Arrays.asList(0, 1, 0)));
int k = 3;
// Function call
System.out.println(maxCount(mat, k));
}
}
// This code is contributed by avanitrachhadiya2155
Python3
# Python3 implementation to find the # maximum count of 1's in # submatrix of order K # Function to find the maximum # count of 1's in the # submatrix of order K def maxCount(mat, k): n, m = len(mat), len(mat[0]) a =[] # Loop to find the count of 1's # in every possible windows # of rows of matrix for e in range(n): s = mat[e] q =[] c = 0 # Loop to find the count of # 1's in the first window for i in range(k): if s[i] == 1: c += 1 q.append(c) p = s[0] # Loop to find the count of # 1's in the remaining windows for j in range(i + 1, m): if s[j]==1: c+= 1 if p ==1: c-= 1 q.append(c) p = s[j-k + 1] a.append(q) b =[] max = 0 # Loop to find the count of 1's # in every possible submatrix for i in range(len(a[0])): c = 0 p = a[0][i] # Loop to find the count of # 1's in the first window for j in range(k): c+= a[j][i] q =[] if c>max: max = c q.append(c) # Loop to find the count of # 1's in the remaining windows for l in range(j + 1, n): c+= a[l][i] c-= p p = a[l-k + 1][i] q.append(c) if c > max: max = c b.append(q) return max # Driver Code if __name__ == "__main__": mat = [[1, 0, 1], [1, 1, 0], [0, 1, 0]] k = 3 # Function call print(maxCount(mat, k))
C#
// C# implementation to find the
// maximum count of 1's in
// submatrix of order K
using System;
using System.Collections.Generic;
class GFG{
// Function to find the maximum
// count of 1's in the
// submatrix of order K
static int maxCount(List<List<int>> mat, int k)
{
int n = mat.Count;
int m = mat[0].Count;
List<List<int>> a = new List<List<int>>();
// Loop to find the count of 1's
// in every possible windows
// of rows of matrix
for(int e = 0; e < n; ++e)
{
List<int> s = mat[e];
List<int> q = new List<int>();
int c = 0;
// Loop to find the count of
// 1's in the first window
int i;
for(i = 0; i < k; ++i)
{
if (s[i] == 1)
{
c++;
}
}
q.Add(c);
int p = s[0];
// Loop to find the count of
// 1's in the remaining windows
for(int j = i + 1; j < m; ++j)
{
if (s[j] == 1)
{
c++;
}
if (p == 1)
{
c--;
}
q.Add(c);
p = s[j - k + 1];
}
a.Add(q);
}
List<List<int>> b = new List<List<int>>();
int max = 0;
// Loop to find the count of 1's
// in every possible submatrix
for(int i = 0; i < a[0].Count; ++i)
{
int c = 0;
int p = a[0][i];
// Loop to find the count of
// 1's in the first window
int j;
for(j = 0; j < k; ++j)
{
c += a[j][i];
}
List<int> q = new List<int>();
if (c > max)
{
max = c;
}
q.Add(c);
// Loop to find the count of
// 1's in the remaining windows
for(int l = j + 1; j < n; ++j)
{
c += a[l][i];
c -= p;
p = a[l - k + 1][i];
q.Add(c);
if (c > max)
{
max = c;
}
}
b.Add(q);
}
return max;
}
// Driver code
static public void Main()
{
List<List<int>> mat = new List<List<int>>();
mat.Add(new List<int>(){1, 0, 1});
mat.Add(new List<int>(){1, 1, 0});
mat.Add(new List<int>(){0, 1, 0});
int k = 3;
// Function call
Console.WriteLine(maxCount(mat, k));
}
}
// This code is contributed by rag2127
Javascript
<script>
// Javascript implementation to find the
// maximum count of 1's in
// submatrix of order K
// Function to find the maximum
// count of 1's in the
// submatrix of order K
function maxCount(mat,k)
{
let n = mat.length;
let m = mat[0].length;
let a = [];
// Loop to find the count of 1's
// in every possible windows
// of rows of matrix
for(let e = 0; e < n; ++e)
{
let s = mat[e];
let q = [];
let c = 0;
// Loop to find the count of
// 1's in the first window
let i;
for(i = 0; i < k; ++i)
{
if (s[i] == 1)
{
c += 1;
}
}
q.push(c);
let p = s[0];
// Loop to find the count of
// 1's in the remaining windows
for(let j = i + 1; j < m; ++j)
{
if (s[j] == 1)
{
c += 1;
}
if (p == 1)
{
c -= 1;
}
q.push(c);
p = s[j - k + 1];
}
a.push(q);
}
let b = [];
let max = 0;
// Loop to find the count of 1's
// in every possible submatrix
for(let i = 0; i < a[0].length; ++i)
{
let c = 0;
let p = a[0][i];
// Loop to find the count of
// 1's in the first window
let j;
for(j = 0; j < k; ++j)
{
c += a[j][i];
}
let q = [];
if (c > max)
{
max = c;
}
q.push(c);
// Loop to find the count of
// 1's in the remaining windows
for(let l = j + 1; j < n; ++j)
{
c += a[l][i];
c -= p;
p = a[l - k + 1][i];
q.push(c);
if (c > max)
{
max = c;
}
}
b.push(q);
}
return max;
}
// Driver code
let mat=[[1, 0, 1],[1, 1, 0],[0, 1, 0]];
let k = 3;
// Function call
document.write(maxCount(mat, k));
// This code is contributed by unknown2108
</script>
Producción:
5
Análisis de rendimiento:
- Complejidad del tiempo: como en el enfoque anterior, hay dos bucles que requieren un tiempo O(N*M), por lo que la complejidad del tiempo será O(N*M) .
- Complejidad espacial: como en el enfoque anterior, se utiliza espacio adicional, por lo tanto, la complejidad espacial será O(N) .
Enfoque 2: [Método de programación dinámica] En esta técnica, calculamos la array dp[][] usando la array mat[][] dada. En la array dp[][] calculamos el número de 1 hasta el índice (i, j) usando el valor dp[][] anterior y guárdelo en dp[i][j] .
Algoritmo:
1) Construct a dp[][] matrix and assign all elements to 0
initial dp[0][0] = mat[0][0]
a) compute first row and column of the dp matrix:
i) for first row:
dp[0][i] = dp[0][i-1] + mat[0][i]
ii) for first column:
dp[i][0] = dp[i-1][0] + mat[i][0]
b) now compute remaining dp matrix from (1,1) to (n,m):
dp[i][j] = mat[i][j] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
2)now, we find the maximum 1's in k X k sub matrix:
a) initially we assign max = dp[k-1][k-1]
b) now first we have to check maximum for k-1 row and k-1 column:
i) for k-1 row:
if dp[k-1][j] - dp[k-1][j-k] > max:
max = dp[k-1][j] - dp[k-1][j-k]
ii) for k-1 column:
if dp[i][k-1] - dp[i-k][k-1] > max:
max = dp[i][k-1] - dp[i-k][k-1]
c) now, we check max for (k to n) row and (k to m) column:
for i from k to n-1:
for j from k to m-1:
if dp[i][j] + dp[i-k][j-k] - dp[i-k][j] - dp[i][j-k] > max:
max = dp[i][j] + dp[i-k][j-k] - dp[i-k][j] - dp[i][j-k]
now just return the max value.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++14 approach
#include <bits/stdc++.h>
using namespace std;
int findMaxK(vector<vector<int>> dp,
int k, int n, int m)
{
// Assign first kXk matrix initial
// value as max
int max_ = dp[k - 1][k - 1];
for(int i = k; i < n; i++)
{
int su = dp[i - k][k - 1];
if (max_ < su)
max_ = su;
}
for(int j = k; j < m; j++)
{
int su = dp[k - 1][j - k];
if (max_< su)
max_ = su;
}
for(int i = k; i < n; i++)
{
for(int j = k; j < m; j++)
{
int su = dp[i][j] +
dp[i - k][j - k] -
dp[i - k][j] -
dp[i][j - k];
if( max_ < su)
max_ = su;
}
}
return max_;
}
vector<vector<int>> buildDPdp(vector<vector<int>> mat,
int k, int n, int m)
{
// Assign mXn dp list to 0
vector<vector<int>> dp(n, vector<int>(m, 0));
// Assign initial starting value
dp[0][0] = mat[0][0];
for(int i = 1; i < m; i++)
dp[0][i] += (dp[0][i - 1] + mat[0][i]);
for(int i = 1; i < n; i++)
dp[i][0] += (dp[i - 1][0] + mat[i][0]);
for(int i = 1; i < n; i++)
for(int j = 1; j < m; j++)
dp[i][j] = dp[i - 1][j] +
dp[i][j - 1] +
mat[i][j] -
dp[i - 1][j - 1];
return dp;
}
int maxOneInK(vector<vector<int>> mat, int k)
{
// n is columns
int n = mat.size();
// m is rows
int m = mat[0].size();
// Build dp list
vector<vector<int>> dp = buildDPdp(
mat, k, n, m);
// Call the function and return its value
return findMaxK(dp, k, n, m);
}
// Driver Code
int main()
{
// mXn matrix
vector<vector<int>> mat = { { 1, 0, 1 },
{ 1, 1, 0 },
{ 0, 1, 0 } };
int k = 3;
// Calling function
cout << maxOneInK(mat, k);
return 0;
}
// This code is contributed by mohit kumar 29
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
static int findMaxK(int[][] dp,
int k, int n, int m)
{
// Assign first kXk matrix initial
// value as max
int max_ = dp[k - 1][k - 1];
for(int i = k; i < n; i++)
{
int su = dp[i - k][k - 1];
if (max_ < su)
max_ = su;
}
for(int j = k; j < m; j++)
{
int su = dp[k - 1][j - k];
if (max_< su)
max_ = su;
}
for(int i = k; i < n; i++)
{
for(int j = k; j < m; j++)
{
int su = dp[i][j] +
dp[i - k][j - k] -
dp[i - k][j] -
dp[i][j - k];
if( max_ < su)
max_ = su;
}
}
return max_;
}
static int[][] buildDPdp(int[][] mat,
int k, int n, int m)
{
// Assign mXn dp list to 0
int[][] dp=new int[n][m];
// Assign initial starting value
dp[0][0] = mat[0][0];
for(int i = 1; i < m; i++)
dp[0][i] += (dp[0][i - 1] + mat[0][i]);
for(int i = 1; i < n; i++)
dp[i][0] += (dp[i - 1][0] + mat[i][0]);
for(int i = 1; i < n; i++)
for(int j = 1; j < m; j++)
dp[i][j] = dp[i - 1][j] +
dp[i][j - 1] +
mat[i][j] -
dp[i - 1][j - 1];
return dp;
}
static int maxOneInK(int[][] mat, int k)
{
// n is columns
int n = mat.length;
// m is rows
int m = mat[0].length;
// Build dp list
int[][] dp = buildDPdp(
mat, k, n, m);
// Call the function and return its value
return findMaxK(dp, k, n, m);
}
// Driver code
public static void main (String[] args)
{
// mXn matrix
int[][] mat = { { 1, 0, 1 },
{ 1, 1, 0 },
{ 0, 1, 0 } };
int k = 3;
// Calling function
System.out.println( maxOneInK(mat, k));
}
}
// This code is contributed by ab2127.
Python3
#python3 approach def findMaxK(dp,k,n,m): # assign first kXk matrix initial value as max max_ = dp[k-1][k-1] for i in range(k,n): su = dp[i-k][k-1] if max_ < su: max_ = su for j in range(k,m): su = dp[k-1][i-k] if max_< su: max_ = su for i in range(k,n): for j in range(k,m): su = dp[i][j] + dp[i-k][j-k] - dp[i-k][j] - dp[i][j-k] if max_ < su: max_ = su return max_ def buildDPdp(mat,k,n,m): # assign mXn dp list to 0 dp = [[0 for i in range(m)] for j in range(n)] # assign initial starting value dp[0][0] = mat[0][0] for i in range(1,m): dp[0][i] += (dp[0][i-1]+mat[0][i]) for i in range(1,n): dp[i][0] += (dp[i-1][0]+mat[i][0]) for i in range(1,n): for j in range(1,m): dp[i][j] = dp[i-1][j] + dp[i][j-1] + mat[i][j] - dp[i-1][j-1] return dp def maxOneInK(mat,k): # n is columns n = len(mat) # m is rows m = len(mat[0]) #build dp list dp = buildDPdp(mat,k,n,m) # call the function and return its value return findMaxK(dp,k,n,m) def main(): # mXn matrix mat = [[1, 0, 1], [1, 1, 0], [0, 1, 0]] k = 3 #callind function print(maxOneInK(mat,k)) #driver code main() #This code is contributed by Tokir Manva
Javascript
<script>
// Javascript approach
function findMaxK(dp, k, n, m)
{
// Assign first kXk matrix initial
// value as max
let max_ = dp[k - 1][k - 1];
for(let i = k; i < n; i++)
{
let su = dp[i - k][k - 1];
if (max_ < su)
max_ = su;
}
for(let j = k; j < m; j++)
{
let su = dp[k - 1][j - k];
if (max_< su)
max_ = su;
}
for(let i = k; i < n; i++)
{
for(let j = k; j < m; j++)
{
let su = dp[i][j] +
dp[i - k][j - k] -
dp[i - k][j] -
dp[i][j - k];
if( max_ < su)
max_ = su;
}
}
return max_;
}
function buildDPdp( mat,k,n,m)
{
// Assign mXn dp list to 0
let dp=new Array(n);
for(let i=0;i<n;i++)
{
dp[i]=new Array(m);
for(let j=0;j<m;j++)
{
dp[i][j]=0;
}
}
// Assign initial starting value
dp[0][0] = mat[0][0];
for(let i = 1; i < m; i++)
dp[0][i] += (dp[0][i - 1] + mat[0][i]);
for(let i = 1; i < n; i++)
dp[i][0] += (dp[i - 1][0] + mat[i][0]);
for(let i = 1; i < n; i++)
for(let j = 1; j < m; j++)
dp[i][j] = dp[i - 1][j] +
dp[i][j - 1] +
mat[i][j] -
dp[i - 1][j - 1];
return dp;
}
function maxOneInK(mat,k)
{
// n is columns
let n = mat.length;
// m is rows
let m = mat[0].length;
// Build dp list
let dp = buildDPdp(
mat, k, n, m);
// Call the function and return its value
return findMaxK(dp, k, n, m);
}
// Driver Code
// mXn matrix
let mat = [[ 1, 0, 1 ],[ 1, 1, 0 ],
[ 0, 1, 0 ]];
let k = 3;
// Calling function
document.write(maxOneInK(mat, k));
// This code is contributed by patel2127
</script>
Producción:
5
Análisis de rendimiento:
- Complejidad del tiempo: como en el enfoque del programa dinámico anterior, tenemos que calcular la array NXM dp que toma el tiempo O (N * M), por lo tanto, la complejidad del tiempo será O (N * M) .
- Complejidad espacial: como en el enfoque anterior, se usa espacio adicional para hacer la array dp NXM , por lo tanto, la complejidad espacial será O (N * M) .