Dada una matriz, ¿qué es un algoritmo para identificar la submatriz con la suma máxima?

Resolví un tipo similar de pregunta sobre Hackerrank.
Trataré de responder todos los métodos posibles que sean posibles. El enfoque ingenuo para esta pregunta lo resuelve en tiempo O (n ^ 3). Pero al definir un mejor algoritmo, es posible resolver esto en O (n) tiempo.
Discutiré todos los enfoques posibles (del ingenuo al mejor)

Algoritmo 1
Un algoritmo sencillo para resolver el problema es recorrer todas las formas posibles de seleccionar una submatriz, calcular la suma de los números en cada submatriz y mantener la suma máxima. El siguiente código implementa este algoritmo:
int p = 0;
para (int a = 1; a <= n; a ++)
{
para (int b = a; b <= n; b ++)
{
int s = 0;
para (int c = a; c <= b; c ++)
{s + = x [c];
}
p = max (p, s);
}
}
cout << p << "\ n";

El código supone que los números se almacenan en una matriz x con los índices 1 … n. Las variables a y b determinan el primer y último número en la submatriz, y la suma de los números se calcula para la variable s. La variable p contiene la suma máxima encontrada durante la búsqueda. La complejidad temporal del algoritmo es O (n3), porque consta de tres bucles anidados que pasan por la entrada
Algoritmo 2
Es fácil hacer que el primer algoritmo sea más eficiente eliminando un bucle. Esto es posible calculando la suma al mismo tiempo cuando se mueve el extremo derecho de la submatriz. El resultado es el siguiente código:

int p = 0;
para (int a = 1; a <= n; a ++)
{
int s = 0; para (int b = a; b <= n; b ++)
{s + = x [b]; p = max (p, s); }
}
cout << p << "\ n";

Después de este cambio, la complejidad del tiempo es O (n2).
Algoritmo 3 (solución O (n))
Es posible resolver esto en O (n) tiempo,
lo que significa que podemos eliminar un bucle más. La idea es calcular, para cada posición de matriz, la suma máxima de una submatriz que termina en esa posición. Después de esto, la respuesta al problema es el máximo de esas sumas. Considere el subproblema de encontrar la submatriz de suma máxima que termina en la posición k. Hay dos posibilidades:
1. La submatriz solo contiene el elemento en la posición k.
2. La submatriz consiste en una submatriz que termina en la posición k − 1, seguida del elemento en la posición k.
Nuestro objetivo es encontrar un subconjunto con suma máxima, por lo que en el caso 2 el subconjunto que termina en la posición k − 1 también debe tener la suma máxima. Por lo tanto, podemos resolver el problema de manera eficiente cuando calculamos la suma máxima de subarreglos para cada posición final de izquierda a derecha. El siguiente código implementa el algoritmo:

int p = 0, s = 0;
para (int k = 1; k <= n; k ++)
{
s = max (x [k], s + x [k]); // esta es la línea principal del código
p = max (p, s);
}
cout << p << "\ n";

El algoritmo solo contiene un bucle que pasa por la entrada, por lo que la complejidad del tiempo es O (n). Esta es también la mejor complejidad de tiempo posible, porque cualquier algoritmo para el problema tiene que examinar todos los elementos de la matriz al menos una vez.

Espero haberlo explicado bien 🙂