Angenommen Matrix Finden 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 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 enthält die Summe der Elemente in der Zeile zwischen den beiden Spalten.
Wenn die Matrix gegeben ist durch:
Dann für das Spaltenpaar Die maximale Submatrixsumme kann mithilfe des 1D-Algorithmus für das Array (von oben nach unten) ermittelt werden:
quelle
Antworten:
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 gibtO ( nm2) und Unter kubische Algorithmen für dieses Problem (im allgemeinen Fall), zum Beispiel Tadao Takaoka ‚sO (n3LogLognLogn- -- -- -- -- -- -√) Algorithmus.
Ich habe auch einen Forumkommentar gefunden, der besagt, dass dieses Problem in gelöst werden kannO (N.2LogN.) für Matrizen mit N Nicht-Null-Elementen unter Verwendung eines "lustigen" Segmentbaums (Sie können den Kommentator nach Details fragen ).
quelle