Maksymalna suma spójnego podciągu

Podciągi o zadanych własnościach - Algorytmy: zakres rozszerzony (Python)

Algorytm Kadane szuka fragmentu o największej sumie jednym przejściem. Zmienna `current` to najlepsza suma fragmentu kończącego się na bieżącym elemencie: albo dokładamy element do poprzedniego fragmentu, albo zaczynamy od niego nowy, jeśli poprzednia suma była ujemna.

data = [2, -5, 6, -2, 3, -1, 4, -7, 1]
current = best = data[0]
for x in data[1:]:
    current = max(x, current + x)
    best = max(best, current)
    print(x, "->", current)
print("największa suma:", best)

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Algorytmy: zakres rozszerzony·Zaloguj się, aby zapisać postęp na koncie.