Dada una Matrix arr[][] de tamaño M x N que tiene números enteros positivos y un número K , la tarea es encontrar el tamaño de la subarray cuadrada más grande cuya suma de elementos es menor o igual a K .
Ejemplo:
Input:
arr[][] = { { 1, 1, 3, 2, 4, 3, 2 },
{ 1, 1, 3, 2, 4, 3, 2 },
{ 1, 1, 3, 2, 4, 3, 2 } },
K = 4
Output:
2
Explanation:
Maximum size square Sub-Matrix
with sum less than or equals to 4
1 1
1 1
Size is 2.
Input:
arr[][] = { { 1, 1, 3, 2, 4, 3, 2 },
{ 1, 1, 3, 2, 4, 3, 2 },
{ 1, 1, 3, 2, 4, 3, 2 } },
K = 22
Output:
3
Explanation:
Maximum size square Sub-Matrix
with sum less than or equals to 22
1 1 3
1 1 3
1 1 3
Size is 3.
Acercarse:
- Para la array dada arr[][], cree una array de suma de prefijos (por ejemplo , sum[][] ) tal que sum[i][j] almacene la suma de todos los elementos de la array de tamaño ixj .
- Para cada fila en la array de suma de prefijos sum [][] utilizando la búsqueda binaria , haga lo siguiente:
- Realice una búsqueda binaria con el límite inferior como 0 y el límite superior en cuanto al tamaño máximo de la array cuadrada .
- Encuentre el índice medio (digamos mid ).
- Si la suma de los elementos de todas las arrays cuadradas posibles de tamaño mid es menor o igual a K , entonces actualice el límite inferior como mid + 1 para encontrar la suma máxima con un tamaño mayor que mid.
- De lo contrario, actualice el límite superior como mid – 1 para encontrar la suma máxima con un tamaño inferior a mid.
- Siga actualizando el tamaño máximo de la array cuadrada en cada iteración para la condición válida anterior.
A continuación se muestra la implementación del enfoque anterior:
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to find the maximum size
// of matrix with sum <= K
static void findMaxMatrixSize(int[][] arr, int K)
{
int i, j;
// N size of rows and M size of cols
int n = arr.length;
int m = arr[0].length;
// To store the prefix sum of matrix
int[][] sum = new int[n + 1][m + 1];
// Create prefix sum
for (i = 0; i <= n; i++) {
// Traverse each rows
for (j = 0; j <= m; j++) {
if (i == 0 || j == 0) {
sum[i][j] = 0;
continue;
}
// Update the prefix sum
// till index i x j
sum[i][j] = arr[i - 1][j - 1]
+ sum[i - 1][j] + sum[i][j - 1]
- sum[i - 1][j - 1];
}
}
// To store the maximum size of
// matrix with sum <= K
int ans = 0;
// Traverse the sum matrix
for (i = 1; i <= n; i++) {
for (j = 1; j <= m; j++) {
// Index out of bound
if (i + ans - 1 > n || j + ans - 1 > m)
break;
int mid, lo = ans;
// Maximum possible size
// of matrix
int hi = Math.min(n - i + 1, m - j + 1);
// Binary Search
while (lo < hi) {
// Find middle index
mid = (hi + lo + 1) / 2;
// Check whether sum <= K
// or not
// If Yes check for other
// half of the search
if (sum[i + mid - 1][j + mid - 1]
+ sum[i - 1][j - 1]
- sum[i + mid - 1][j - 1]
- sum[i - 1][j + mid - 1]
<= K) {
lo = mid;
}
// Else check it in first
// half
else {
hi = mid - 1;
}
}
// Update the maximum size matrix
ans = Math.max(ans, lo);
}
}
// Print the final answer
System.out.print(ans + "\n");
}
// Driver Code
public static void main(String[] args)
{
int[][] arr = { { 1, 1, 3, 2, 4, 3, 2 },
{ 1, 1, 3, 2, 4, 3, 2 },
{ 1, 1, 3, 2, 4, 3, 2 } };
// Given target sum
int K = 4;
// Function Call
findMaxMatrixSize(arr, K);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach # Function to find the maximum size # of matrix with sum <= K def findMaxMatrixSize(arr, K): # N size of rows and M size of cols n = len(arr) m = len(arr[0]) # To store the prefix sum of matrix sum = [[0 for i in range(m + 1)] for j in range(n + 1)] # Create Prefix Sum for i in range(n + 1): # Traverse each rows for j in range(m+1): if (i == 0 or j == 0): sum[i][j] = 0 continue # Update the prefix sum # till index i x j sum[i][j] = arr[i - 1][j - 1] + sum[i - 1][j] + \ sum[i][j - 1]-sum[i - 1][j - 1] # To store the maximum size of # matrix with sum <= K ans = 0 # Traverse the sum matrix for i in range(1, n + 1): for j in range(1, m + 1): # Index out of bound if (i + ans - 1 > n or j + ans - 1 > m): break mid = ans lo = ans # Maximum possible size # of matrix hi = min(n - i + 1, m - j + 1) # Binary Search while (lo < hi): # Find middle index mid = (hi + lo + 1) // 2 # Check whether sum <= K # or not # If Yes check for other # half of the search if (sum[i + mid - 1][j + mid - 1] + sum[i - 1][j - 1] - sum[i + mid - 1][j - 1] - sum[i - 1][j + mid - 1] <= K): lo = mid # Else check it in first # half else: hi = mid - 1 # Update the maximum size matrix ans = max(ans, lo) # Print the final answer print(ans) # Driver Code if __name__ == '__main__': arr = [[1, 1, 3, 2, 4, 3, 2], [1, 1, 3, 2, 4, 3, 2], [1, 1, 3, 2, 4, 3, 2]] # Given target sum K = 4 # Function Call findMaxMatrixSize(arr, K) # This code is contributed by Surendra_Gangwar
C#
// C# program for the above approach
using System;
class GFG {
// Function to find the maximum size
// of matrix with sum <= K
static void findMaxMatrixSize(int[, ] arr, int K)
{
int i, j;
// N size of rows and M size of cols
int n = arr.GetLength(0);
int m = arr.GetLength(1);
// To store the prefix sum of matrix
int[, ] sum = new int[n + 1, m + 1];
// Create prefix sum
for (i = 0; i <= n; i++) {
// Traverse each rows
for (j = 0; j <= m; j++) {
if (i == 0 || j == 0) {
sum[i, j] = 0;
continue;
}
// Update the prefix sum
// till index i x j
sum[i, j] = arr[i - 1, j - 1]
+ sum[i - 1, j] + sum[i, j - 1]
- sum[i - 1, j - 1];
}
}
// To store the maximum size
// of matrix with sum <= K
int ans = 0;
// Traverse the sum matrix
for (i = 1; i <= n; i++) {
for (j = 1; j <= m; j++) {
// Index out of bound
if (i + ans - 1 > n || j + ans - 1 > m)
break;
int mid, lo = ans;
// Maximum possible size
// of matrix
int hi = Math.Min(n - i + 1, m - j + 1);
// Binary Search
while (lo < hi) {
// Find middle index
mid = (hi + lo + 1) / 2;
// Check whether sum <= K
// or not
// If Yes check for other
// half of the search
if (sum[i + mid - 1, j + mid - 1]
+ sum[i - 1, j - 1]
- sum[i + mid - 1, j - 1]
- sum[i - 1, j + mid - 1]
<= K) {
lo = mid;
}
// Else check it in first
// half
else {
hi = mid - 1;
}
}
// Update the maximum size matrix
ans = Math.Max(ans, lo);
}
}
// Print the readonly answer
Console.Write(ans + "\n");
}
// Driver Code
public static void Main(String[] args)
{
int[, ] arr = { { 1, 1, 3, 2, 4, 3, 2 },
{ 1, 1, 3, 2, 4, 3, 2 },
{ 1, 1, 3, 2, 4, 3, 2 } };
// Given target sum
int K = 4;
// Function Call
findMaxMatrixSize(arr, K);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// js program for the above approach
// Function to find the maximum size
// of matrix with sum <= K
function findMaxMatrixSize(arr, K)
{
let i, j;
// N size of rows and M size of cols
let n = arr.length;
let m = arr[0].length;
// To store the prefix sum of matrix
let sum=[];
for(i =0;i<n+1;i++){
sum[i] = [];
for(j =0;j<m+1;j++){
sum[i][j] = 0;
}
}
// Create Prefix Sum
for ( i = 0; i <= n; i++) {
// Traverse each rows
for (j = 0; j <= m; j++) {
if (i == 0 || j == 0) {
sum[i][j] = 0;
continue;
}
// Update the prefix sum
// till index i x j
sum[i][j] = arr[i - 1][j - 1] + sum[i - 1][j]
+ sum[i][j - 1] - sum[i - 1][j - 1];
}
}
// To store the maximum size of
// matrix with sum <= K
let ans = 0;
// Traverse the sum matrix
for (i = 1; i <= n; i++) {
for (j = 1; j <= m; j++) {
// Index out of bound
if (i + ans - 1 > n || j + ans - 1 > m)
break;
let mid, lo = ans;
// Maximum possible size
// of matrix
let hi = Math.min(n - i + 1, m - j + 1);
// Binary Search
while (lo < hi) {
// Find middle index
mid = Math.floor((hi + lo + 1) / 2);
// Check whether sum <= K
// or not
// If Yes check for other
// half of the search
if (sum[i + mid - 1][j + mid - 1]
+ sum[i - 1][j - 1]
- sum[i + mid - 1][j - 1]
- sum[i - 1][j + mid - 1]
<= K) {
lo = mid;
}
// Else check it in first
// half
else {
hi = mid - 1;
}
}
// Update the maximum size matrix
ans = Math.max(ans, lo);
}
}
// Print the final answer
document.write(ans ,'<br>');
}
// Driver Code
let arr = [[ 1, 1, 3, 2, 4, 3, 2 ],
[ 1, 1, 3, 2, 4, 3, 2 ],
[ 1, 1, 3, 2, 4, 3, 2 ]];
// Given target sum
let K = 4;
// Function Call
findMaxMatrixSize(arr, K);
</script>
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum size
// of matrix with sum <= K
void findMaxMatrixSize(vector<vector<int> > arr, int K)
{
int i, j;
// N size of rows and M size of cols
int n = arr.size();
int m = arr[0].size();
// To store the prefix sum of matrix
int sum[n + 1][m + 1];
// Create Prefix Sum
for (int i = 0; i <= n; i++) {
// Traverse each rows
for (int j = 0; j <= m; j++) {
if (i == 0 || j == 0) {
sum[i][j] = 0;
continue;
}
// Update the prefix sum
// till index i x j
sum[i][j] = arr[i - 1][j - 1] + sum[i - 1][j]
+ sum[i][j - 1] - sum[i - 1][j - 1];
}
}
// To store the maximum size of
// matrix with sum <= K
int ans = 0;
// Traverse the sum matrix
for (i = 1; i <= n; i++) {
for (j = 1; j <= m; j++) {
// Index out of bound
if (i + ans - 1 > n || j + ans - 1 > m)
break;
int mid, lo = ans;
// Maximum possible size
// of matrix
int hi = min(n - i + 1, m - j + 1);
// Binary Search
while (lo < hi) {
// Find middle index
mid = (hi + lo + 1) / 2;
// Check whether sum <= K
// or not
// If Yes check for other
// half of the search
if (sum[i + mid - 1][j + mid - 1]
+ sum[i - 1][j - 1]
- sum[i + mid - 1][j - 1]
- sum[i - 1][j + mid - 1]
<= K) {
lo = mid;
}
// Else check it in first
// half
else {
hi = mid - 1;
}
}
// Update the maximum size matrix
ans = max(ans, lo);
}
}
// Print the final answer
cout << ans << endl;
}
// Driver Code
int main()
{
vector<vector<int> > arr;
arr = { { 1, 1, 3, 2, 4, 3, 2 },
{ 1, 1, 3, 2, 4, 3, 2 },
{ 1, 1, 3, 2, 4, 3, 2 } };
// Given target sum
int K = 4;
// Function Call
findMaxMatrixSize(arr, K);
return 0;
}
Producción
2
Complejidad de tiempo: O(N*N*log(N))
Espacio auxiliar: O(M*N)