sumaryczny podwzrost sumy w rzadkiej macierzy

Question

Wyznaczenie maksymalnego sumarycznego sumy w macierzy NxN można wykonać za pomocą algorytmu 2-d kadane, jak wskazano w innych wpisach. Jednakże, jeśli macierz jest rzadka, konkretnie O(n) niezerowych wpisów, czy można pokonać czas ?

Jeśli to pomoże, dla aktualnej aplikacji jestem zainteresowany, to wystarczy mieć rozwiązanie, które przyjmuje co najwyżej jedną niezerową wartość w każdym wierszu i każdej kolumnie macierzy. Jednak w moich przyszłych zastosowaniach to założenie może nie być odpowiednie (wystarczy tylko sparyność), a poza tym moja matematyczna intuicja podpowiada, że ​​mogą istnieć dobre rozwiązania, które po prostu wykorzystują rzadkość i nie wykorzystują dalej faktu, że macierz jest iloczyn macierzy diagonalnej i permutacyjnej.

Answer 1

Tak, można to zrobić lepiej.

Przede wszystkim pomyślmy o strukturze danych, która pozwala nam

1. zaktualizować każdy pojedynczy wartości instrumentu bazowego 1D tablicy w O(logn) czasie
2. Znajdź sumę maksymalnej subarray tablicy w O(1) czas

Właściwie, zrównoważone drzewo binarne, które wygląda jak poniżej, może wykonać zadanie. Struktura drzewa może być opisana jako:

1. Każdy węzeł liści drzewa reprezentuje każdy element tablicy.
2. Jeśli wewnętrzny węzeł obejmuje zakres [a, b], jego lewe dziecko obejmuje zakres [a, c], a jego prawy pokrowiec obejmuje zakres [c + 1, b], gdzie c = floor((a + b)/2)).

3. Główny węzeł obejmuje zakres [1, n].

        O 
           / \ 
          /  \ 
          /   \ 
         /    \ 
         /     \ 
         O      O 
        / \     / \ 
       / \    / \ 
       /  \    /  \ 
       O   O   O   O 
   /\  /\  /\  /\ 
   o  o  o  o  o  o  o  o 
   A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] 
   

Istnieją 4 pola dołączone do każdego węzła v (w tym węzłów liściowych i węzłów wewnętrznych):

• S[v]: suma wszystkich wartości w v „s zakresie
• M[v] : maksymalna suma podciągów w zakresie v:
• L[v]: suma maksym m subarray, który rozpoczyna się po lewej stronie v „zakresie s
• R[v]: suma maksymalnej subarray że kończy się na prawej stronie v” s Zakres

Na podstawie powyższych definicji, możemy znaleźć następujące zasady aktualizacji:

• Dla każdego węzła liścia v, S[v] = A[v], M[v] = L[v] = R[v] = max{0, A[v]}
• Dla każdego wewnętrznego węzła v i jej dzieci l i r,
  
  • S[v] = S[l] + S[r]
  • M[v] = max{M[l], M[r], R[l] + L[r]}
  • L[v] = max{L[l], L[r] + S[l]}
  • R[v] = max{R[r], R[l] + S[r]}

Wreszcie możemy realizować operacje wymienione na początku.

• Aby zaktualizować A[i], możemy znaleźć odpowiedni węzeł liścia w drzewie i zaktualizować pola wzdłuż jego ścieżki do korzenia przy użyciu powyższych zasad.
• Maksymalna suma podobrazów to po prostu M[root].

Porozmawiajmy teraz o tym, jak znaleźć maksymalny prostokąt za pomocą tej struktury danych. Jeśli ustawimy górny i dolny rząd prostokąta na i th i j th wierszy, problem zmieni się w sumę problemów pod sumą 1D, gdzie A[k] = sum{B[i..j, k]}. Kluczowym wglądem jest to, że dla ustalonego i, jeśli wymienimy j w porządku rosnącym, możemy wykorzystać powyższą strukturę danych do utrzymania podstawowej tablicy 1D i znaleźć odpowiedź bardzo szybko. Pseudokod opisuje pomysł:

result = 0 
for i in (1, 2, ..., n) 
    set all fields of the binary tree T to 0 
    for j in (i, i + 1, ..., n) 
     for any k where B[j, k] != 0 
      T.update(k, A[k] + B[j, k]) 
     result = max{M[root], result} 
return result 

Załóżmy, że matryca zawiera m niezerowe elementy złożoność czasowa tego algorytmu jest O(mn logn). W twoim przypadku m = O(n), więc złożoność czasu wynosi O(n^2 logn) i jest lepsza niż O(n^3).