Spis treściKliknij link, aby przejść do wybranego miejsca
Ta treść została automatycznie przetłumaczona z ukraińskiego.
Rozważmy klasyczny problem z algorytmów: znaleźć podtablicę o maksymalnej sumie.
Warunki zadania
Mamy tablicę liczb całkowitych (pozytywnych, negatywnych lub zerowych). Należy znaleźć taką ciągłą podsekwencję (subarray), której suma jest maksymalna możliwa.
max_sequence([-2, 1, -3, 4, -1, 2, 1, -5, 4]) # => 6, ponieważ największa suma to [4, -1, 2, 1]
Ważne punkty:
- Jeśli wszystkie liczby są negatywne — zwracamy 0.
- Pusta tablica również zwraca 0.
- Podtablica musi być ciągła (to znaczy wszystkie elementy obok siebie).
Zasada rozwiązania (Algorytm Kadane’a)
Będziemy poruszać się po tablicy z lewej do prawej, a na każdym kroku:
- Dodajemy bieżącą liczbę do sumy pośredniej current_sum.
- Jeśli current_sum stała się mniejsza od 0 — zerujemy ją.
- Zapamiętujemy największą wartość current_sum, która się pojawiła — to jest nasza odpowiedź.
Jeśli suma stała się mniejsza od 0, pogarsza ona następne wartości, dlatego ją resetujemy.
Implementacja w Ruby(jak zawsze, to jedna z możliwych wersji implementacji)
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 dla metody Ruby
RSpec.describe '#max_sequence' do
it 'zwraca maksymalną sumę ciągłej podsekwencji' 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
Proste wyjaśnienie
Wyobraźmy sobie, że przechodzimy przez tablicę i gromadzimy sumę. Ale jeśli w pewnym momencie ta suma stała się ujemna — to wszystko, dalej tylko przeszkadza. Resetujemy ją i próbujemy ponownie.
Można wyobrazić sobie, że szukamy najkorzystniejszego odcinka drogi — gdzie zdobyliśmy najwięcej "punktów", nie pozwalając stracić wszystkiego przez jedną złą dziurę.
Ten algorytm nadaje się do problemów typu "znajdź największą podsekwencję". Działa w O(n) — czyli bardzo szybko. Prosty do zaimplementowania i przetestowania.
Ten post nie ma jeszcze żadnych dodatków od autora.
