Jak możemy znaleźć maksymalną sumę aniezmniejszająca się podsekwencja w tablicy przy użyciu drzewa Fenwicka? Na przykład mamy 1 4 4 2 2 3 3 1, tutaj maksymalna suma nie malejącej pod-sekwencji wynosi 11 (1 2 2 3 3).
Odpowiedzi:
1 dla odpowiedzi № 1Maksymalną sumę można znaleźć za pomocą dynamicznejalgorytm programowania. Zeskanuj tablicę i dla każdego elementu dodaj jego wartość do największej ważnej sumy pod-sekwencji (podsekwencja kończy się wartością nie większą niż ten element).
Skuteczne wdrożenie wymaga jakiegoś sposobuszybko znajdź maksymalną wartość w podanym podzakresie. Można do tego wykorzystać rozszerzone drzewo wyszukiwania binarnego. Drzewo Fenwicka to po prostu wydajna implementacja rozszerzonego drzewa wyszukiwania binarnego. Najczęstszym zastosowaniem drzewa Fenwicka jest znalezienie sumy wartości w pewnym podzakresie. Trywialna modyfikacja pozwala na jej użycie do znalezienia maksimum podzakresu (to działa, ponieważ w tym konkretnym przypadku wartości w drzewie Fenwicka nigdy nie są zmniejszane).
Zobacz ten kod Pythona, aby uzyskać szczegółowe informacje:
array = [1, 4, 4, 2, 2, 3, 3, 1]
numbers = sorted(set(array))
n = len(numbers)
indexes = {numbers[v]:v+1 for v in range(0, n)}
n += 1
bit = [0] * n
result = 0
for x in array:
pos = indexes[x]
i = pos
maximum = 0
while i != 0:
maximum = max(maximum, bit[i])
i = i & (i-1)
x += maximum
i = pos
while i < n:
bit[i] = max(bit[i], x)
i += i & -i
result = max(result, x)
print(result)
indexes słownik służy do zmniejszania rozmiaru drzewa Fenwicka z największej liczby w tablicy wejściowej do rozmiaru tablicy. Najpierw zagnieżdżone while znajduje maksimum podzakresu w drzewie Fenwicka. Drugi zagnieżdżony while aktualizuje drzewo Fenwicka po zaktualizowaniu jednej z sum.
Ten kod działa tylko dla tablicy liczb dodatnich. W ogólnym przypadku tablica wejściowa powinna zostać wstępnie przetworzona przez odfiltrowanie wszystkich liczb niedodatnich.
Złożoność czasowa wynosi O (N log N). Złożoność przestrzeni to O (N).