InhaltsverzeichnisKlicke auf den Link, um zur gewünschten Stelle zu navigieren
Dieser Inhalt wurde automatisch aus dem Ukrainischen übersetzt.
Betrachten wir das klassische Problem aus der Algorithmik: das Teilarray mit der maximalen Summe finden.
Aufgabenstellung
Wir haben ein Array von ganzen Zahlen (positiv, negativ oder null). Wir müssen eine kontinuierliche Teilfolge (subarray) finden, deren Summe möglichst maximal ist.
max_sequence([-2, 1, -3, 4, -1, 2, 1, -5, 4]) # => 6, weil die größte Summe [4, -1, 2, 1] ist
Wichtige Punkte:
- Wenn alle Zahlen negativ sind — geben wir 0 zurück.
- Ein leeres Array gibt ebenfalls 0 zurück.
- Das Teilarray muss kontinuierlich sein (d.h. alle Elemente hintereinander).
Lösungsprinzip (Kadane-Algorithmus)
Wir werden von links nach rechts durch das Array gehen und bei jedem Schritt:
- Die aktuelle Zahl zur Zwischensumme current_sum hinzufügen.
- Wenn current_sum kleiner als 0 wird — setzen wir sie auf 0.
- Wir merken uns den größten Wert von current_sum, der bisher aufgetreten ist — das ist unsere Antwort.
Wenn die Summe kleiner als 0 wird, verschlechtert sie die folgenden Werte, daher setzen wir sie zurück.
Implementierung in Ruby(wie immer, dies ist eine der möglichen Implementierungen)
def max_sequence(arr)
max_sum = 0
current_sum = 0
arr.each do |n|
current_sum += n
max_sum = [max_sum, current_sum].max
current_sum = 0 if current_sum < 0
end
max_sum
end
Rspec für die Ruby-Methode
RSpec.describe '#max_sequence' do
it 'gibt die maximale Summe einer zusammenhängenden Teilfolge zurück' do
expect(max_sequence([])).to eq(0)
expect(max_sequence([-1, -2, -3])).to eq(0)
expect(max_sequence([1, 2, 3])).to eq(6)
expect(max_sequence([-2, 1, -3, 4, -1, 2, 1, -5, 4])).to eq(6)
expect(max_sequence([2, -1, 2, 3, 4, -5])).to eq(10)
expect(max_sequence([-2, -3, 4, -1, -2, 1, 5, -3])).to eq(7)
end
end
Einfache Erklärung
Stellen wir uns vor, wir gehen durch das Array und summieren die Werte. Aber wenn diese Summe irgendwann negativ wird — dann ist es vorbei, sie wird nur noch stören. Wir setzen sie zurück und versuchen es erneut.
Man kann sich vorstellen, dass wir den vorteilhaftesten Abschnitt der Straße suchen — wo wir die meisten "Punkte" gesammelt haben, ohne alles durch ein einziges schlechtes Loch zu verlieren.
Dieser Algorithmus eignet sich für Probleme vom Typ "finde die größte Teilfolge". Er arbeitet in O(n) — also sehr schnell. Einfach zu implementieren und zu testen.
Dieser Beitrag hat noch keine Ergänzungen vom Autor.
