Finden einer Submatrix mit der maximal möglichen Summe in O (n ^ 2)
Ich versuche, ein Programm in Java zu schreiben, das bei einer gegebenen MxN-Matrix die (zusammenhängende) Untermatrix mit der größten Zahlensumme findet. Das Programm muss dann die Koordinaten der oberen linken Ecke der Untermatrix und die Koordinaten der unteren rechten Ecke zurückgeben. Die Matrix kann negative Zahlen enthalten und sowohl die Matrix als auch die Untermatrix müssen nicht quadratisch sein.
Ich sah, dass dies hier diskutiert wurde:Holen Sie sich die Submatrix mit der maximalen Summe? und die Lösung scheint O (n ^ 3) zu sein. Ein Freund von mir sagte, dass es ihnen einmal gelungen sei, dieses Problem in O (n ^ 2) zu lösen. Auch vorgeschlagenHier Ist das möglich
Gibt es irgendeinen verfügbaren Code, der dieses Problem auf die effizienteste Weise löst?