Dada una array mat[][] cuyos elementos se ordenan tanto por filas como por columnas. La tarea es encontrar la suma máxima de cualquier subarray de la array dada mat[][] .
Ejemplos:
Entrada: mat[][] = { {-6, -4, -1}, {-3, 2, 4}, {2, 5, 8}}
Salida: 19
Explicación:
La subarray más grande está dada por:
2 4
5 8
Entrada: mat[][] = { {-4, -3}, {-2, -1} }
Salida: -1
Explicación:
La subarray que consta del último elemento, es decir, -1 tiene la suma más grande posible.
Enfoque ingenuo: la idea es encontrar el rectángulo de suma máxima en una array 2D utilizando el algoritmo de Kadane . Imprime la suma máxima obtenida.
Complejidad de tiempo: O(N 2 *M 2 ), donde N es el número de filas y M es el número de columnas
Espacio auxiliar: O(N)
Enfoque eficiente: La idea es encontrar la suma máxima de la celda inferior de la array y use Programación Dinámica para almacenar la suma máxima de cualquier subarray de la celda inferior. A continuación se muestran los pasos:
- Cree una tabla dp dp[][] de tamaño NxM para almacenar la suma máxima de subarray a partir de cada celda (i, j) .
- Encuentre la suma de la subarray comenzando desde la celda inferior derecha (N, M) hacia arriba y hacia la izquierda y siga actualizando la suma máxima a dp[][] .
- Dado que la array está ordenada por filas y columnas, la suma más grande de la subarray puede comenzar desde cualquier punto, pero definitivamente terminará en la celda inferior derecha (N, M).
- A continuación se muestra la relación de cómo se llena la tabla dp:
DP[i][j] = DP[i+1][j] + DP[i][j+1] – DP[i+1][j+1]
- Por lo tanto, encuentre el elemento máximo en la tabla dp.
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 that finds the maximum
// Sub-Matrix Sum
int maxSubMatSum(vector<vector<int> > mat)
{
// Number of rows in the matrix
int n = mat.size();
// Number of columns in the matrix
int m = mat[0].size();
int i, j;
// dp[][] matrix to store the
// results of each iteration
int dp[n][m];
// Base Case - The largest
// element in the matrix
dp[n - 1][m - 1] = mat[n - 1][m - 1];
// To stores the final result
int res = dp[n - 1][m - 1];
// Find the max sub matrix sum for
// the last row
for (i = m - 2; i >= 0; i--) {
dp[n - 1][i] = mat[n - 1][i]
+ dp[n - 1][i + 1];
// Check whether the current
// sub-array yields maximum sum
res = max(res, dp[n - 1][i]);
}
// Calculate the max sub matrix
// sum for the last column
for (i = n - 2; i >= 0; i--) {
dp[i][m - 1] = mat[i][m - 1]
+ dp[i + 1][m - 1];
// Check whether the current
// sub-array yields maximum sum
res = max(res, dp[i][m - 1]);
}
// Build the dp[][] matrix from
// bottom to the top row
for (i = n - 2; i >= 0; i--) {
for (j = m - 2; j >= 0; j--) {
// Update sum at each
// cell in dp[][]
dp[i][j]
= mat[i][j] + dp[i][j + 1]
+ dp[i + 1][j]
- dp[i + 1][j + 1];
// Update the maximum sum
res = max(res, dp[i][j]);
}
}
// Return the maximum sum
return res;
}
// Driver Code
int main()
{
// Given matrix mat[][]
vector<vector<int> > mat;
mat = { { -6, -4, -1 },
{ -3, 2, 4 },
{ 2, 5, 8 } };
// Function Call
cout << maxSubMatSum(mat);
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function that finds the maximum
// Sub-Matrix Sum
static int maxSubMatSum(int [][]mat)
{
// Number of rows in the matrix
int n = mat.length;
// Number of columns in the matrix
int m = mat[0].length;
int i, j;
// dp[][] matrix to store the
// results of each iteration
int [][]dp = new int[n][m];
// Base Case - The largest
// element in the matrix
dp[n - 1][m - 1] = mat[n - 1][m - 1];
// To stores the final result
int res = dp[n - 1][m - 1];
// Find the max sub matrix sum for
// the last row
for (i = m - 2; i >= 0; i--)
{
dp[n - 1][i] = mat[n - 1][i] +
dp[n - 1][i + 1];
// Check whether the current
// sub-array yields maximum sum
res = Math.max(res, dp[n - 1][i]);
}
// Calculate the max sub matrix
// sum for the last column
for (i = n - 2; i >= 0; i--)
{
dp[i][m - 1] = mat[i][m - 1] +
dp[i + 1][m - 1];
// Check whether the current
// sub-array yields maximum sum
res = Math.max(res, dp[i][m - 1]);
}
// Build the dp[][] matrix from
// bottom to the top row
for (i = n - 2; i >= 0; i--)
{
for (j = m - 2; j >= 0; j--)
{
// Update sum at each
// cell in dp[][]
dp[i][j] = mat[i][j] + dp[i][j + 1] +
dp[i + 1][j] - dp[i + 1][j + 1];
// Update the maximum sum
res = Math.max(res, dp[i][j]);
}
}
// Return the maximum sum
return res;
}
// Driver Code
public static void main(String[] args)
{
// Given matrix mat[][]
int [][]mat= {{ -6, -4, -1 },
{ -3, 2, 4 },
{ 2, 5, 8 } };
// Function Call
System.out.print(maxSubMatSum(mat));
}
}
// This code is contributed by Rohit_ranjan
Python3
# Python3 program for the above approach # Function that finds the maximum # Sub-Matrix Sum def maxSubMatSum(mat): # Number of rows in the matrix n = len(mat) # Number of columns in the matrix m = len(mat[0]) # dp[][] matrix to store the # results of each iteration dp = [[0] * m for _ in range(n)] # Base Case - The largest # element in the matrix dp[n - 1][m - 1] = mat[n - 1][m - 1] # To stores the final result res = dp[n - 1][m - 1] # Find the max sub matrix sum for # the last row for i in range(m - 2, -1, -1): dp[n - 1][i] = (mat[n - 1][i] + dp[n - 1][i + 1]) # Check whether the current # sub-array yields maximum sum res = max(res, dp[n - 1][i]) # Calculate the max sub matrix # sum for the last column for i in range(n - 2, -1, -1): dp[i][m - 1] = (mat[i][m - 1] + dp[i + 1][m - 1]) # Check whether the current # sub-array yields maximum sum res = max(res, dp[i][m - 1]) # Build the dp[][] matrix from # bottom to the top row for i in range(n - 2, -1, -1): for j in range(m - 2, -1, -1): # Update sum at each # cell in dp[][] dp[i][j] = (mat[i][j] + dp[i][j + 1] + dp[i + 1][j]- dp[i + 1][j + 1]) # Update the maximum sum res = max(res, dp[i][j]) # Return the maximum sum return res # Driver Code if __name__ == '__main__': # Given matrix mat[][] mat = [ [ -6, -4, -1 ], [ -3, 2, 4 ], [ 2, 5, 8 ] ] # Function call print(maxSubMatSum(mat)) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
// Function that finds the maximum
// Sub-Matrix Sum
static int maxSubMatSum(int [,]mat)
{
// Number of rows in the matrix
int n = mat.GetLength(0);
// Number of columns in the matrix
int m = mat.GetLength(1);
int i, j;
// [,]dp matrix to store the
// results of each iteration
int [,]dp = new int[n, m];
// Base Case - The largest
// element in the matrix
dp[n - 1, m - 1] = mat[n - 1, m - 1];
// To stores the readonly result
int res = dp[n - 1, m - 1];
// Find the max sub matrix sum for
// the last row
for (i = m - 2; i >= 0; i--)
{
dp[n - 1, i] = mat[n - 1, i] +
dp[n - 1, i + 1];
// Check whether the current
// sub-array yields maximum sum
res = Math.Max(res, dp[n - 1,i]);
}
// Calculate the max sub matrix
// sum for the last column
for (i = n - 2; i >= 0; i--)
{
dp[i, m - 1] = mat[i, m - 1] +
dp[i + 1, m - 1];
// Check whether the current
// sub-array yields maximum sum
res = Math.Max(res, dp[i, m - 1]);
}
// Build the [,]dp matrix from
// bottom to the top row
for (i = n - 2; i >= 0; i--)
{
for (j = m - 2; j >= 0; j--)
{
// Update sum at each
// cell in [,]dp
dp[i, j] = mat[i, j] + dp[i, j + 1] +
dp[i + 1, j] - dp[i + 1, j + 1];
// Update the maximum sum
res = Math.Max(res, dp[i, j]);
}
}
// Return the maximum sum
return res;
}
// Driver Code
public static void Main(String[] args)
{
// Given matrix [,]mat
int [,]mat= {{ -6, -4, -1 },
{ -3, 2, 4 },
{ 2, 5, 8 } };
// Function Call
Console.Write(maxSubMatSum(mat));
}
}
// This code is contributed by Rohit_ranjan
Javascript
<script>
// Javascript program for the above approach
// Function that finds the maximum
// Sub-Matrix Sum
function maxSubMatSum(mat)
{
// Number of rows in the matrix
var n = mat.length;
// Number of columns in the matrix
var m = mat[0].length;
var i, j;
// dp matrix to store the
// results of each iteration
var dp = Array(n).fill().map(() =>
Array(m).fill(0));
// Base Case - The largest
// element in the matrix
dp[n - 1][m - 1] = mat[n - 1][m - 1];
// To stores the final result
var res = dp[n - 1][m - 1];
// Find the max sub matrix sum for
// the last row
for (i = m - 2; i >= 0; i--) {
dp[n - 1][i] = mat[n - 1][i] +
dp[n - 1][i + 1];
// Check whether the current
// sub-array yields maximum sum
res = Math.max(res, dp[n - 1][i]);
}
// Calculate the max sub matrix
// sum for the last column
for (i = n - 2; i >= 0; i--) {
dp[i][m - 1] = mat[i][m - 1] +
dp[i + 1][m - 1];
// Check whether the current
// sub-array yields maximum sum
res = Math.max(res, dp[i][m - 1]);
}
// Build the dp matrix from
// bottom to the top row
for (i = n - 2; i >= 0; i--) {
for (j = m - 2; j >= 0; j--) {
// Update sum at each
// cell in dp
dp[i][j] = mat[i][j] + dp[i][j + 1] +
dp[i + 1][j] - dp[i + 1][j + 1];
// Update the maximum sum
res = Math.max(res, dp[i][j]);
}
}
// Return the maximum sum
return res;
}
// Driver Code
// Given matrix mat
var mat = [ [ -6, -4, -1 ],
[ -3, 2, 4 ],
[ 2, 5, 8 ] ];
// Function Call
document.write(maxSubMatSum(mat));
// This code contributed by umadevi9616
</script>
Producción:
19
Complejidad de Tiempo: O(N*M), donde N es el número de filas y M es el número de columnas
Espacio Auxiliar: O(N*M)