Dada una array mat[][] de tamaño N x M y una array queries[] de tamaño Q, que contiene (a, b) pares . La tarea es encontrar la suma máxima entre todas las subarrays (axb) de la array mat[][] .
Nota: Las filas y columnas de la subarray deben ser contiguas.
Ejemplos:
Entrada: N = 3, M = 4, Q = 1, consultas[] = {(3, 2)}
mat[][] = {{1, 2, 3, 9},
{4, 5, 6, 2 },
{8, 3, 2, 6}}
Salida: 28
Explicación :
Aquí a = 3 y b = 2
La primera subarray de 3×2 es:
1 2
4 5
8 3
La suma de los elementos en esta es 23.
La segunda La subarray de 3×2 es:
2 3
5 6
3 2
La suma de elementos en esto es 21.
La tercera subarray de 3×2 es:
3 9
6 2
2 6
La suma de elementos en esto es 28.
El máximo entre estos es 28 .Entrada : N = 3, M = 4, Q = 3, consultas[] = {(1, 1), (2, 2), (3, 3)}
mat[][] = {{1, 2, 3 , 9},
{4, 5, 6, 2},
{8, 3, 2, 6}}
Salida : 9 20 38
Enfoque ingenuo: el enfoque más simple para resolver este problema es para cada consulta, encuentre la suma de cada subarray e imprima la más grande.
Complejidad temporal: O(Q*(N*M)^2), donde Q es el número de consultas, N y M son el número de filas y columnas de la array mat[][].
Espacio Auxiliar: O(1)
Enfoque eficiente: este problema se puede resolver realizando un procesamiento previo antes de responder a todas las consultas . Siga los pasos a continuación para resolver este problema:
- Declare una array 2D , dp donde dp[i][j] almacena la suma de elementos desde (0, 0) hasta (i, j).
- Realice un preprocesamiento para input mat[][]. Declare una función, digamos, preProcess(mat, dp, n, m), siga los siguientes pasos:
- Iterar en el rango [0, m-1] usando la variable i y Actualizar dp[0][i] como mat[0][i].
- Iterar en el rango [1, n-1] usando la variable i :
- Iterar en el rango [0, m-1] usando la variable j:
- Actualice dp[i][j] a dp[i-1][j] + mat[i][j].
- Iterar en el rango [0, m-1] usando la variable j:
- Iterar en el rango [0, n-1] usando la variable i :
- Iterar en el rango [1, m-1] usando la variable j:
- Actualice dp[i][j] a dp[i][j] + dp[i][j-1].
- Iterar en el rango [1, m-1] usando la variable j:
- Declare una array , maxSum para almacenar la respuesta para cada consulta.
- Declare una función, por ejemplo, sumQuery(dp, tli, tlj, rbi, rbj), donde tli y tlj son el número de fila y el número de columna de la parte superior izquierda de la subarray de consulta, respectivamente, rbi y rbj son el número de fila y el número de columna de la parte inferior derecha de la subarray de consulta, que calcula la suma de la subarray en tiempo O(1) .
- Inicialice una variable res como dp[rbi][rbj] para almacenar la suma de la subarray.
- Si tl i es mayor que 0 , elimine los elementos entre (0, 0) y (tli-1, rbj) .
- Si tlj es mayor que 0, elimine elementos entre (0, 0) y (rbi, tlj-1).
- Si tli es mayor que 0 y tlj es mayor que 0, agregue dp[tli-1][tlj-1] ya que los elementos entre (0, 0) y (tli-1, tlj-1) se restan dos veces.
- Iterar en el rango [0, q-1] usando la variable qi :
- Iterar en el rango [0, n-consultas[qi][0]] usando la variable i:
- Iterar en el rango [0, m-consultas[qi][1]] usando la variable j :
- Actualice maxSum[qi] al máximo de maxSum[qi] y sumQuery(dp, i, j, i + consultas[qi][0] – 1, j + consultas[qi][1] – 1)).
- Iterar en el rango [0, m-consultas[qi][1]] usando la variable j :
- Iterar en el rango [0, n-consultas[qi][0]] usando la variable i:
- Después de completar los pasos anteriores, imprima la array maxSum como la respuesta para cada consulta.
Referencia: https://www.geeksforgeeks.org/submatrix-sum-queries/
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to preprocess input mat[N][M].
// This function mainly fills dp[N][M]
// such that dp[i][j] stores sum
// of elements from (0, 0) to (i, j)
void preProcess(vector<vector<int>> &mat,
vector<vector<int>> &dp,
int n, int m)
{
// Copy first row of mat[][] to dp[][]
for(int i = 0; i < m; i++)
{
dp[0][i] = mat[0][i];
}
// Do column wise sum
for(int i = 1; i < n; i++)
{
for(int j = 0; j < m; j++)
{
dp[i][j] = dp[i - 1][j] + mat[i][j];
}
}
// Do row wise sum
for(int i = 0; i < n; i++)
{
for(int j = 1; j < m; j++)
{
dp[i][j] += dp[i][j - 1];
}
}
}
// A O(1) time function to compute sum of submatrix
// between (tli, tlj) and (rbi, rbj) using dp[][]
// which is built by the preprocess function
int sumQuery(vector<vector<int>> dp, int tli,
int tlj, int rbi, int rbj)
{
// Result is now sum of elements
// between (0, 0) and (rbi, rbj)
int res = dp[rbi][rbj];
// Remove elements between (0, 0)
// and (tli-1, rbj)
if (tli > 0)
res = res - dp[tli - 1][rbj];
// Remove elements between (0, 0)
// and (rbi, tlj-1)
if (tlj > 0)
res = res - dp[rbi][tlj - 1];
// Add dp[tli-1][tlj-1] as elements
// between (0, 0) and (tli-1, tlj-1)
// are subtracted twice
if (tli > 0 && tlj > 0)
res = res + dp[tli - 1][tlj - 1];
return res;
}
// Function to find the maximum sum
// among all (a x b) sub-matrices of the matrix
vector<int> maxSubMatrixSumQueries(vector<vector<int>> mat,
int n, int m,
vector<vector<int>> queries,
int q)
{
vector<vector<int> > dp(n, vector<int>(m));
// Function call
preProcess(mat, dp, n, m);
vector<int> maxSum((int)queries.size());
// Run a loop for finding
// answer for all queries
for(int qi = 0; qi < q; qi++)
{
for(int i = 0; i < n - queries[qi][0] + 1; i++)
{
for(int j = 0; j < m - queries[qi][1] + 1; j++)
{
maxSum[qi] = max(maxSum[qi],
sumQuery(dp, i, j,
i + queries[qi][0] - 1,
j + queries[qi][1] - 1));
}
}
}
return maxSum;
}
// Driver Code
int main()
{
// Given input
int n = 3, m = 4;
vector<vector<int> > mat = { { 1, 2, 3, 9 },
{ 4, 5, 6, 2 },
{ 8, 3, 2, 6 } };
int Q = 3;
vector<vector<int> >Queries = { { 1, 1 },
{ 2, 2 },
{ 3, 3 } };
// Function call
vector<int> maxSum = maxSubMatrixSumQueries(
mat, n, m, Queries, Q);
// Print answer for all queries
for(int i = 0; i < Q; i++)
{
cout << maxSum[i] << " ";
}
}
// This code is contributed by mohit kumar 29
Java
// Java program for the above approach
public class Solution {
// Function to preprocess input mat[N][M].
// This function mainly fills dp[N][M]
// such that dp[i][j] stores sum
// of elements from (0, 0) to (i, j)
static void preProcess(int mat[][], int dp[][],
int n, int m)
{
// Copy first row of mat[][] to dp[][]
for (int i = 0; i < m; i++) {
dp[0][i] = mat[0][i];
}
// Do column wise sum
for (int i = 1; i < n; i++) {
for (int j = 0; j < m; j++) {
dp[i][j] = dp[i - 1][j] + mat[i][j];
}
}
// Do row wise sum
for (int i = 0; i < n; i++) {
for (int j = 1; j < m; j++) {
dp[i][j] += dp[i][j - 1];
}
}
}
// A O(1) time function to compute sum of submatrix
// between (tli, tlj) and (rbi, rbj) using dp[][]
// which is built by the preprocess function
static int sumQuery(int dp[][], int tli,
int tlj, int rbi,
int rbj)
{
// Result is now sum of elements
// between (0, 0) and (rbi, rbj)
int res = dp[rbi][rbj];
// Remove elements between (0, 0)
// and (tli-1, rbj)
if (tli > 0)
res = res - dp[tli - 1][rbj];
// Remove elements between (0, 0)
// and (rbi, tlj-1)
if (tlj > 0)
res = res - dp[rbi][tlj - 1];
// Add dp[tli-1][tlj-1] as elements
// between (0, 0) and (tli-1, tlj-1)
// are subtracted twice
if (tli > 0 && tlj > 0)
res
= res + dp[tli - 1][tlj - 1];
return res;
}
// Function to find the maximum sum
// among all (a x b) sub-matrices of the matrix
static int[] maxSubMatrixSumQueries(
int[][] mat,
int n, int m,
int[][] queries,
int q)
{
int dp[][] = new int[n][m];
// Function call
preProcess(mat, dp, n, m);
int maxSum[] = new int[queries.length];
// Run a loop for finding
// answer for all queries
for (int qi = 0; qi < q; qi++) {
for (int i = 0; i < n - queries[qi][0] + 1; i++) {
for (int j = 0; j < m - queries[qi][1] + 1; j++) {
maxSum[qi]
= Math.max(maxSum[qi],
sumQuery(dp, i, j,
i + queries[qi][0] - 1,
j + queries[qi][1] - 1));
}
}
}
return maxSum;
}
// Driver Code
public static void main(String args[])
{
// Given input
int n = 3, m = 4;
int mat[][] = { { 1, 2, 3, 9 },
{ 4, 5, 6, 2 },
{ 8, 3, 2, 6 } };
int Q = 3;
int Queries[][] = { { 1, 1 },
{ 2, 2 },
{ 3, 3 } };
// Function call
int maxSum[]
= maxSubMatrixSumQueries(
mat, n, m, Queries, Q);
// Print answer for all queries
for (int i = 0; i < Q; i++) {
System.out.print(maxSum[i] + " ");
}
}
}
Python3
# Python program for the above approach # Function to preprocess input mat[N][M]. # This function mainly fills dp[N][M] # such that dp[i][j] stores sum # of elements from (0, 0) to (i, j) def preProcess(mat, dp, n, m): # Copy first row of mat[][] to dp[][] for i in range(m): dp[0][i] = mat[0][i] # Do column wise sum for i in range(1, n): for j in range(m): dp[i][j] = dp[i - 1][j] + mat[i][j] # Do row wise sum for i in range(n): for j in range(1, m): dp[i][j] += dp[i][j - 1] # A O(1) time function to compute sum of submatrix # between (tli, tlj) and (rbi, rbj) using dp[][] # which is built by the preprocess function def sumQuery(dp, tli, tlj, rbi, rbj): # Result is now sum of elements # between (0, 0) and (rbi, rbj) res = dp[rbi][rbj] # Remove elements between (0, 0) # and (tli-1, rbj) if (tli > 0): res = res - dp[tli - 1][rbj] # Remove elements between (0, 0) # and (rbi, tlj-1) if (tlj > 0): res = res - dp[rbi][tlj - 1] # Add dp[tli-1][tlj-1] as elements # between (0, 0) and (tli-1, tlj-1) # are subtracted twice if (tli > 0 and tlj > 0): res = res + dp[tli - 1][tlj - 1] return res # Function to find the maximum sum # among all (a x b) sub-matrices of the matrix def maxSubMatrixSumQueries(mat, n, m, queries, q): dp = [[0 for i in range(m)] for j in range(n)] # Function call preProcess(mat, dp, n, m) maxSum = [0]*len(queries) # Run a loop for finding # answer for all queries for qi in range(q): for i in range(n - queries[qi][0] + 1): for j in range(m - queries[qi][1] + 1): maxSum[qi] = max(maxSum[qi], sumQuery(dp, i, j, i + queries[qi][0] - 1, j + queries[qi][1] - 1)) return maxSum # Driver Code # Given input n = 3 m = 4 mat = [[1, 2, 3, 9], [4, 5, 6, 2], [8, 3, 2, 6]] Q = 3 Queries = [[1, 1], [2, 2], [3, 3]] # Function call maxSum = maxSubMatrixSumQueries(mat, n, m, Queries, Q) # Print answer for all queries print(*maxSum) # This code is comntributed by Lovely Jain
C#
using System;
public class GFG{
// Function to preprocess input mat[N][M].
// This function mainly fills dp[N][M]
// such that dp[i][j] stores sum
// of elements from (0, 0) to (i, j)
static void preProcess(int[,] mat, int[,] dp,
int n, int m)
{
// Copy first row of mat[][] to dp[][]
for (int i = 0; i < m; i++) {
dp[0,i] = mat[0,i];
}
// Do column wise sum
for (int i = 1; i < n; i++) {
for (int j = 0; j < m; j++) {
dp[i,j] = dp[i - 1,j] + mat[i,j];
}
}
// Do row wise sum
for (int i = 0; i < n; i++) {
for (int j = 1; j < m; j++) {
dp[i,j] += dp[i,j - 1];
}
}
}
// A O(1) time function to compute sum of submatrix
// between (tli, tlj) and (rbi, rbj) using dp[][]
// which is built by the preprocess function
static int sumQuery(int[,] dp, int tli,
int tlj, int rbi,
int rbj)
{
// Result is now sum of elements
// between (0, 0) and (rbi, rbj)
int res = dp[rbi,rbj];
// Remove elements between (0, 0)
// and (tli-1, rbj)
if (tli > 0)
res = res - dp[tli - 1,rbj];
// Remove elements between (0, 0)
// and (rbi, tlj-1)
if (tlj > 0)
res = res - dp[rbi,tlj - 1];
// Add dp[tli-1][tlj-1] as elements
// between (0, 0) and (tli-1, tlj-1)
// are subtracted twice
if (tli > 0 && tlj > 0)
res
= res + dp[tli - 1,tlj - 1];
return res;
}
// Function to find the maximum sum
// among all (a x b) sub-matrices of the matrix
static int[] maxSubMatrixSumQueries(
int[,] mat,
int n, int m,
int[,] queries,
int q)
{
int[,] dp = new int[n,m];
// Function call
preProcess(mat, dp, n, m);
int[] maxSum = new int[queries.GetLength(0)];
// Run a loop for finding
// answer for all queries
for (int qi = 0; qi < q; qi++) {
for (int i = 0; i < n - queries[qi,0] + 1; i++) {
for (int j = 0; j < m - queries[qi,1] + 1; j++) {
maxSum[qi]
= Math.Max(maxSum[qi],
sumQuery(dp, i, j,
i + queries[qi,0] - 1,
j + queries[qi,1] - 1));
}
}
}
return maxSum;
}
// Driver Code
static public void Main (){
// Given input
int n = 3, m = 4;
int[,] mat = { { 1, 2, 3, 9 },
{ 4, 5, 6, 2 },
{ 8, 3, 2, 6 } };
int Q = 3;
int[,] Queries = { { 1, 1 },
{ 2, 2 },
{ 3, 3 } };
// Function call
int[] maxSum
= maxSubMatrixSumQueries(
mat, n, m, Queries, Q);
// Print answer for all queries
for (int i = 0; i < Q; i++) {
Console.Write(maxSum[i] + " ");
}
}
}
// This code is contributed by patel2127.
Javascript
<script>
// JavaScript program for the above approach
// Function to preprocess input mat[N][M].
// This function mainly fills dp[N][M]
// such that dp[i][j] stores sum
// of elements from (0, 0) to (i, j)
function preProcess(mat, dp, n, m)
{
// Copy first row of mat[][] to dp[][]
for(let i = 0; i < m; i++)
{
dp[0][i] = mat[0][i];
}
// Do column wise sum
for(let i = 1; i < n; i++)
{
for(let j = 0; j < m; j++)
{
dp[i][j] = dp[i - 1][j] + mat[i][j];
}
}
// Do row wise sum
for(let i = 0; i < n; i++)
{
for(let j = 1; j < m; j++)
{
dp[i][j] += dp[i][j - 1];
}
}
}
// A O(1) time function to compute sum of submatrix
// between (tli, tlj) and (rbi, rbj) using dp[][]
// which is built by the preprocess function
function sumQuery(dp, tli, tlj, rbi, rbj)
{
// Result is now sum of elements
// between (0, 0) and (rbi, rbj)
let res = dp[rbi][rbj];
// Remove elements between (0, 0)
// and (tli-1, rbj)
if (tli > 0)
res = res - dp[tli - 1][rbj];
// Remove elements between (0, 0)
// and (rbi, tlj-1)
if (tlj > 0)
res = res - dp[rbi][tlj - 1];
// Add dp[tli-1][tlj-1] as elements
// between (0, 0) and (tli-1, tlj-1)
// are subtracted twice
if (tli > 0 && tlj > 0)
res = res + dp[tli - 1][tlj - 1];
return res;
}
// Function to find the maximum sum
// among all (a x b) sub-matrices of the matrix
function maxSubMatrixSumQueries(mat, n, m, queries, q)
{
let dp = Array(n).fill().map(() => Array(m));
// Function call
preProcess(mat, dp, n, m);
let maxSum = new Array(queries.length).fill(0);
// Run a loop for finding
// answer for all queries
for(let qi = 0; qi < q; qi++)
{
for(let i = 0; i < n - queries[qi][0] + 1; i++)
{
for(let j = 0; j < m - queries[qi][1] + 1; j++)
{
maxSum[qi] = Math.max(maxSum[qi],
sumQuery(dp, i, j,
i + queries[qi][0] - 1,
j + queries[qi][1] - 1));
}
}
}
return maxSum;
}
// Driver code
// Given input
let n = 3, m = 4;
let mat = [ [ 1, 2, 3, 9 ],
[ 4, 5, 6, 2 ],
[ 8, 3, 2, 6 ] ];
let Q = 3;
let Queries = [ [ 1, 1 ],
[ 2, 2 ],
[ 3, 3 ] ];
// Function call
let maxSum = maxSubMatrixSumQueries(
mat, n, m, Queries, Q);
// Print answer for all queries
for(let i = 0; i < Q; i++)
{
document.write(maxSum[i] + " ");
}
// This code is contributed by Potta Lokesh
</script>
Producción
9 20 38
Complejidad temporal: O(Q*N*M), donde Q es el número de consultas, N y M son el número de filas y columnas de la array mat[][].
Espacio auxiliar: O(N*M)
Publicación traducida automáticamente
Artículo escrito por prince18bce183 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA