Maksymalna suma wszystkich podarunków o rozmiarze k dla każdego k = 1.nn.

Question

Biorąc pod uwagę tablicę o rozmiarze n, dla każdego k od 1 do n, znajdź maksymalną sumę sąsiadujących podprzestrzeni o rozmiarze k. Ten problem ma oczywiste rozwiązanie o złożoności czasowej O (N) i O (1) spacji. Kod Lua:

array = {7, 1, 3, 1, 4, 5, 1, 3, 6} 
n = #array 

function maxArray(k) 
    ksum = 0 
    for i = 1, k do 
     ksum = ksum + array[i] 
    end 
    max_ksum = ksum 
    for i = k + 1, n do 
     add_index = i 
     sub_index = i - k 
     ksum = ksum + array[add_index] - array[sub_index] 
     max_ksum = math.max(ksum, max_ksum) 
    end 
    return max_ksum 
end 

for k = 1, n do 
    print(k, maxArray(k)) 
end 

Czy istnieje algorytm o mniejszej złożoności czasu? Na przykład O (N log N) + dodatkowa pamięć.

Powiązane tematy:

• Kadane's algorithm

Answer 1

poniżej procesu może pomóc

1) wybory pierwsze elementy K i tworzą samobalansujący binarne drzewo poszukiwań (BST) w rozmiarze K .

2) Uruchom pętlę dla i = 0 do n - k

... ..a) Get maksymalną elementu z BST, a następnie je wydrukować.

... ..b) Wyszukaj arr [i] w BST i usuń go z BST.

.....c) Wstaw arr [i + k] do BST.

Złożoność czasowa: Złożoność czasowa kroku 1 to O (kLogk). Złożoność czasowa kroków 2 (a), 2 (b) i 2 (c) wynosi O (log). Ponieważ kroki 2 (a), 2 (b) i 2 (c) są w pętli, która działa n-k + 1 razy, złożoność czasu kompletnego algorytmu to O (kLogk + (n-k + 1) * Logk) które można również zapisać jako O (nLogk).

Answer 2

Nie sądzę, że istnieje bardziej wydajne rozwiązanie niż O (N²), jeśli nie doda się żadnego innego ograniczenia. Innymi słowy, nie ma innego sposobu, aby zdecydować, że znalazłeś subarray o sumie maksymalnej, ale aby zbadać wszystkie inne podwarstwy.

Zatem najmniej kompleks roztwór zawiera O (N²/2), które jest całkowitą liczbą sąsiednich subarrays tablicy o określonej długości N.

osobiście będzie implementować to przy zastosowaniu podejścia dynamicznego programowania. Pomysł polega na uzyskaniu klina częściowych wyników i wykorzystaniu ich do zbudowania aktualnych sum podbarw (zamiast obliczania całej sumy). W każdym razie daje to "tylko" stałe przyspieszenie, a więc złożoność wynosi O (N²/2) ~ O (N²).

Oto pseudokod - przepraszam za nie mówiąc Lua

// here we place temporary results, row by row alternating in 0 or 1 
int[2][N] sum_array_buffer 
// stores the start of the max subarray 
int[N] max_subarray_start 
// stores the value 
int[N] max_subarray_value 

array = {7, 1, 3, 1, 4, 5, 1, 3, 6} 
// we initialize the buffer with the array (ideally 1-length subarrays) 
sum_array_buffer[1] = array 
// the length of subarrays - we can also start from 1 if considered 
for k = 1 ; k <= (N); ++k: 
    // the starting position fo the sub-array 
    for j = 0; j < (N-k+1); ++j: 
     sum_array_buffer[k%2][j] = sum_array_buffer[(k+1)%2][j] + array[j+k-1] 
     if j == 0 || sum_array_buffer[k%2][j] > max_subarray_value[k]: 
      max_subarray_value = sum_array_buffer[k%2][j] 
      max_subarray_start[k] = j 


for k = 1 ; k <= (N); ++k: 
    print(k, max_subarray_value[k]) 

Graphycally:

Answer 3

Tworzymy rozkolejkowania Qi zdolności k, który przechowuje tylko użyteczne elementy bieżącym oknie z elementów k. Element jest użyteczny, jeśli znajduje się w bieżącym oknie i jest większy niż wszystkie pozostałe elementy po lewej stronie w bieżącym oknie. Wszystkie elementy tablicy przetwarzamy pojedynczo i utrzymujemy Qi tak, aby zawierała użyteczne elementy bieżącego okna, a te użyteczne elementy są porządkowane w porządku posortowanym. Element z przodu Qi jest największy, a element z tyłu Qi jest najmniejszym z obecnych okien.