Trzy metody, jeden wynik

Porównanie metod algorytmicznych dla jednego problemu - Informatyka - liceum klasa 3, zakres rozszerzony (Python)

Największą sumę spójnego fragmentu listy można policzyć: - **przeglądem zupełnym**: każda para (początek, koniec), około `n²` sum, - **dynamicznie** (algorytm Kadane): jedno przejście, najlepsza suma kończąca się na bieżącym elemencie. Program liczy oba wyniki i liczbę wykonanych dodawań.

data = [3, -5, 4, -1, 2, 6, -9, 3, 1]
ops = 0
best_brute = data[0]
for i in range(len(data)):
    total = 0
    for j in range(i, len(data)):
        total += data[j]
        ops += 1
        best_brute = max(best_brute, total)
print("przegląd:", best_brute, "dodawań:", ops)
ops = 0
current = best = data[0]
for x in data[1:]:
    current = max(x, current + x)
    ops += 1
    best = max(best, current)
print("dynamicznie:", best, "dodawań:", ops)

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

Wszystkie lekcje kursu Informatyka - liceum klasa 3, zakres rozszerzony·Zaloguj się, aby zapisać postęp na koncie.