Maximale Submatrixsumme

7

Angenommen n×m Matrix EINFinden Sie aus ganzen Zahlen eine Untermatrix, deren Summe maximal ist. Wenn nur eine Zeile oder nur eine Spalte vorhanden ist, entspricht dies dem Auffinden eines maximalen Unterarrays .

Die 1D-Version kann durch dynamische Programmierung in linearer Zeit gelöst werden. Die 2D-Version kann in gelöst werdenÖ(n3) durch Schleifen über alle Spaltenpaare und Verwenden des 1D-Algorithmus für das Array, dessen Länge die Anzahl der Zeilen in der Matrix ist, in der sich jede Position befindet r enthält die Summe der Elemente in der Zeile r zwischen den beiden Spalten.

Wenn die Matrix gegeben ist durch:

(1- -20- -15433178- -45- -12199)

Dann für das Spaltenpaar (0,2)Die maximale Submatrixsumme kann mithilfe des 1D-Algorithmus für das Array (von oben nach unten) ermittelt werden:

(1- -2+0=- -15+43+31=79- -45- -12+19=- -38)
Kennt jemand eine Ö(n2) Algorithmus zur Lösung dieses Problems?
saadtaame
quelle
Schauen Sie sich dieses Video an, in dem diese Frage erklärt wird. youtu.be/yCQN096CwWM

Antworten:

2

Ich fand dies: Sung Eun Bae, sequentielle und parallele Algorithmen für das generalisierte Maximum-Subarray-Problem . Lesen Sie die Seiten 18 bis 30, auf denen steht, dass es nur Kubik gibtÖ(nm2)und Unter kubische Algorithmen für dieses Problem (im allgemeinen Fall), zum Beispiel Tadao Takaoka ‚sÖ(n3LogLognLogn) Algorithmus.

Ich habe auch einen Forumkommentar gefunden, der besagt, dass dieses Problem in gelöst werden kannÖ(N.2LogN.)für Matrizen mit N Nicht-Null-Elementen unter Verwendung eines "lustigen" Segmentbaums (Sie können den Kommentator nach Details fragen ).

Ralor
quelle
Das einzige, was ich an dieser Seite hasse, ist, dass sie auf Russisch geschrieben ist (ich benutze sie allerdings oft).
Saadtaame
@saadtaame Ich denke, es ist in PHP geschrieben. Und Sie können Übersetzer verwenden, um auf Russisch geschriebene Texte zu verstehen. Aber ich rate Ihnen, diese Worte "Ich hasse" nicht zu sagen, "Gefühle von Gläubigen nicht zu beleidigen" (rus. Sprichwort). Einige von uns (im Allgemeinen diejenigen, die Fremdsprachen beherrschen) sind sehr stolz auf unsere grenzenlose Sprache (ich auch). А вот это перевести нечерезче.
Ralor
Ich wollte deine Gefühle nicht verletzen, Kumpel, sorry. Ja, ich benutze Übersetzer (ich sagte, dass ich die Seite oft benutze). Sie können uns einen großen Gefallen tun, indem Sie die Website ins Englische übersetzen.
Saadtaame