Estoy tratando de escribir un programa en Java que cuando se le da una matriz MxN encontrará la submatriz (contigua) con la mayor suma de números. El programa debe devolver las coordenadas de la esquina superior izquierda de la submatriz y las coordenadas de la esquina inferior derecha. La matriz puede incluir números negativos y tanto la matriz como la submatriz no necesitan ser cuadradas.

Vi que esto se discutió aquí:¿Conseguir la submatriz con la suma máxima? y la solución parece ser O (n ^ 3). Un amigo mío dijo que una vez habían logrado resolver este problema en O (n ^ 2). También sugeridoaquí. ¿Es eso posible?

¿Existe algún código disponible que resuelva este problema de la manera más eficiente?