← strona głównaProgramowanie (Програмування)

Jak znaleźć podtablicę o maksymalnej sumie (Maximum Subarray Sum) w Ruby

Znajdź podtablicę o maksymalnej sumie w tablicy liczb za pomocą algorytmu Kadane’a. Proste wyjaśnienie, implementacja w Ruby, przykłady i testy. Idealne dla tych, którzy uczą się algorytmów.

22 maj '25 11:01·2 min. czytania

Spis treściKliknij link, aby przejść do wybranego miejsca

Warunki zadania Zasada rozwiązania (Algorytm Kadane’a)Proste wyjaśnienie

Ta treść została automatycznie przetłumaczona z ukraińskiego.

Zobacz oryginał

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.

Programowanie (Програмування)