Maximale Summe aller Unterfelder der Größe k für jedes k = 1..n

Question

Gegeben ein Array der Größe n, für jedes k von 1 bis n, finden Sie die maximale Summe zusammenhängender Subarrays der Größe k.

Dieses Problem hat eine offensichtliche Lösung mit Zeitkomplexität O (N) und O (1) Raum. Lua-Code:

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 

Gibt es einen Algorithmus mit geringerer zeitlicher Komplexität? Zum Beispiel O (N log N) + zusätzlicher Speicher.

Verwandte Themen:

• Kadane's algorithm

Answer 1

unten Prozess könnte Ihnen helfen

1) Wählen ersten k Elemente und schaffen k eine Balancierter Baum (BST) der Größe .

2) Führen einer Schleife für i = 0 bis n - k

... ..A) Erhalten des maximalen Elements aus dem BST, und ausdrucken.

... ..b) Suche nach arr [i] in der BST und lösche es aus der BST.

... ..c) Setzen Sie arr [i + k] in die BST ein.

Zeitkomplexität: Zeit Komplexität von Schritt 1 ist O (kLogk). Zeit Komplexität der Schritte 2 (a), 2 (b) und 2 (c) ist O (Logk). Da die Schritte 2 (a), 2 (b) und 2 (c) in einer Schleife sind, die n-k + 1-mal läuft, ist die Zeitkomplexität des vollständigen Algorithmus O (kLogk + (n - k + 1) · Logk) das kann auch als O (nLogk) geschrieben werden.

Answer 2

Ich glaube nicht, dass es eine effizientere Lösung als O (N²) gibt, wenn Sie keine andere Einschränkung hinzufügen. Mit anderen Worten, es gibt keine andere Möglichkeit, zu entscheiden, dass Sie das Maximum-Subarray gefunden haben, sondern alle anderen Subarrays.

Somit sind die am wenigsten komplexe Lösung umfasst O (N²/2), die die Gesamtzahl von zusammenhängenden Untermatrizen einer Matrix von N. gegebener Länge

persönlich würde ich dies mit dem dynamischen Programmierung Ansatz implementieren ist. Die Idee ist, einen Teil von Teilergebnissen zu haben und sie zu verwenden, um die aktuellen Summen der Teilmatrizen zu bilden (anstatt die gesamte Summe zu berechnen). Jedenfalls gibt es "nur" eine konstante Beschleunigung, daher ist die Komplexität O (N²/2) ~ O (N²).

Hier finden Sie Pseudo-Code - sorry für nicht 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 sprechen:

Answer 3

Wir schaffen eine Dequeue, Qi der Kapazität k, dass Geschäfte nur nützliche Elemente des aktuellen Fensters von k Elementen. Ein Element ist nützlich, wenn es sich im aktuellen Fenster befindet und größer ist als alle anderen Elemente auf der linken Seite im aktuellen Fenster. Wir verarbeiten alle Array-Elemente nacheinander und halten Qi so, dass sie nützliche Elemente des aktuellen Fensters enthalten, und diese nützlichen Elemente werden in sortierter Reihenfolge verwaltet. Das Element an der Vorderseite des Qi ist das größte und das Element an der Rückseite von Qi ist das kleinste des aktuellen Fensters.