Máxima submatriz programacion dinamica
Para encontrar la máxima submatriz en una matriz dada utilizando programación dinámica, puedes seguir el siguiente enfoque:
1. Crea una matriz auxiliar de igual tamaño que la matriz original para almacenar la suma acumulativa de los elementos en la submatriz hasta ese punto.
2. Inicializa la primera fila y la primera columna de la matriz auxiliar con los valores de la matriz original.
3. Para cada celda restante en la matriz auxiliar, calcula la suma acumulativa como la suma del valor actual de la matriz original más el valor de la celda encima y a la izquierda, menos el valor de la celda diagonalmente opuesta (para evitar contar el mismo valor dos veces).
4. Encuentra la submatriz con la suma máxima en la matriz auxiliar y guarda sus coordenadas.
5. Utiliza las coordenadas de la submatriz con la suma máxima para extraer la submatriz correspondiente de la matriz original.
A continuación te muestro un ejemplo de implementación en Python:
```python
def max_submatrix(matrix):
rows = len(matrix)
cols = len(matrix[0])
# Crear matriz auxiliar para almacenar la suma acumulativa
dp = [[0 for _ in range(cols)] for _ in range(rows)]
# Inicializar primera fila y primera columna
for i in range(rows):
dp[i][0] = matrix[i][0]
for j in range(cols):
dp[0][j] = matrix[0][j]
# Calcular suma acumulativa para cada celda
for i in range(1, rows):
for j in range(1, cols):
dp[i][j] = matrix[i][j] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
max_sum = float('-inf')
top, left, bottom, right = 0, 0, 0, 0
# Encontrar submatriz con la suma máxima
for i in range(rows):
for j in range(cols):
for k in range(i, rows):
for l in range(j, cols):
current_sum = dp[k][l]
if i > 0:
current_sum -= dp[i-1][l]
if j > 0:
current_sum -= dp[k][j-1]
if i > 0 and j > 0:
current_sum += dp[i-1][j-1]
if current_sum > max_sum:
max_sum = current_sum
top, left, bottom, right = i, j, k, l
return max_sum, top, left, bottom, right
# Ejemplo de uso
matrix = [
[1, 2, -1, -4, -20],
[-8, -3, 4, 2, 1],
[3, 8, 10, 1, 3],
[-4, -1, 1, 7, -6]
]
max_sum, top, left, bottom, right = max_submatrix(matrix)
print("La máxima submatriz tiene una suma de:", max_sum)
print("Sus coordenadas son: (", top, ",", left, ") - (", bottom, ",", right, ")")
```
Este código implementa el algoritmo descrito anteriormente para encontrar la máxima submatriz en una matriz dada. Puedes probarlo con diferentes matrices para ver cómo funciona.