Algorytmy i struktury danych · Middle · Pytanie 47 z 75
Na czym polega algorytm Kadane'a dla maksymalnej sumy podtablicy?
- 1Posortować tablicę i dodać wszystkie liczby dodatnie
- ✓Poprawna odpowiedź: Najlepsza suma kończąca się tu: przedłużyć lub zacząć od nowa
- 3Sprawdzić sumę każdej możliwej podtablicy
Wyjaśnienie
cur = Math.max(x, cur + x), best = Math.max(best, cur). Ujemna bieżąca suma tylko szkodzi, więc się ją porzuca. Jedno przejście O(n) zamiast O(n²) dla wszystkich podtablic.