Estou tentando escrever um programa em Java que, quando recebe uma matriz MxN, encontrará a submatriz (contígua) com a maior soma de números. O programa precisa retornar as coordenadas do canto superior esquerdo da submatriz e as coordenadas do canto inferior direito. A matriz pode incluir números negativos e a matriz e a submatriz não precisam ser quadradas.

Vi que isso foi discutido aqui:Obtendo a submatriz com soma máxima? e a solução parece haver O (n ^ 3). Um amigo meu disse que uma vez conseguiu resolver esse problema em O (n ^ 2). Também sugeridoaqui. Isso é possível?

Existe algum código disponível por aí que resolva esse problema da maneira mais eficiente?