somma massima subrectangle in una matrice sparsa

Question

La ricerca della somma massima subrectangle in una matrice NxN può essere eseguita nel tempo O(n^3) utilizzando l'algoritmo di kadane 2-d, come indicato in altri post. Tuttavia, se la matrice è sparsa, in particolare O(n) voci diverse da zero, è possibile battere il tempo O(n^3)?

Se è utile, per l'applicazione corrente a cui sono interessato, sarebbe sufficiente disporre di una soluzione che presupponga al massimo un valore diverso da zero in ogni riga e in ciascuna colonna della matrice. Tuttavia, nelle mie future applicazioni questa ipotesi potrebbe non essere appropriata (solo la scarsità si manterrà), e comunque la mia intuizione matematica è che ci possono essere buone soluzioni che sfruttano semplicemente la scarsità e non sfruttano ulteriormente il fatto che la matrice è un prodotto di una diagonale e una matrice di permutazione.

Answer 1

Sì, può essere fatto meglio.

Prima di tutto, pensiamo a una struttura di dati che permette di

1. Aggiorna ogni singolo valore della matrice 1D sottostante O(logn) tempo
2. Trovare la somma di massima sottomatrice della matrice in O(1) time

In realtà, un albero binario bilanciato che appare come sotto può fare il lavoro. La struttura ad albero può essere descritta come:

1. Ogni nodo foglia dell'albero rappresenta ogni elemento dell'array.
2. Se un nodo interno copre l'intervallo [a, b], l'intervallo figlio sinistro è compreso nell'intervallo [a, c] e nell'intervallo di copertura figlio destro [c + 1, b], dove c = floor((a + b)/2)).

3. Il nodo radice copre l'intervallo [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] 
   

Ci sono 4 campi collegate a ciascun nodo v (compresi i nodi foglia e nodi interni):

• S[v]: la somma di tutti i valori nella gamma v s'
• M[v] : la somma massima della subarray nell'intervallo v
• L[v]: la somma di maximu m sottoarray che parte dal lato sinistro del v 'serie s
• R[v]: la somma di massima sottoarray che termina al lato destro del v' serie s

Sulla base delle definizioni di cui sopra, si può trovare la seguenti regole di aggiornamento:

• Per ogni nodo foglia v, S[v] = A[v], M[v] = L[v] = R[v] = max{0, A[v]}
• Per ogni nodo interno v ed i suoi bambini l e 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]}

Infine, possiamo attuare le operazioni di cui all'inizio.

• Per aggiornare A[i], si può trovare il nodo foglia corrispondente nella struttura e aggiornare i campi lungo il suo percorso verso la radice utilizzando le regole di cui sopra.
• La somma massima del subarray è semplicemente M[root].

Ora discutiamo come trovare il rettangolo massimo utilizzando questa struttura dati. Se fissiamo la riga superiore e la riga inferiore del rettangolo a i th e j th rows, il problema diventa il problema di somma massima della subarray 1D, dove A[k] = sum{B[i..j, k]}. L'intuizione chiave è che, per un valore fisso i, se si enumera j in ordine crescente, è possibile utilizzare la struttura dati sopra riportata per mantenere la matrice 1D sottostante e trovare la risposta molto rapidamente. Lo pseudo codice descrive l'idea:

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 

Supponiamo matrice contiene m elementi non nulli, la complessità temporale di questo algoritmo è O(mn logn). Nel tuo caso m = O(n), quindi la complessità temporale è O(n^2 logn) ed è migliore di O(n^3).