Archiwa tagu: podciąg o największej sumie

Ciekawostki

Elegancki algorytm miesiąca: Kadane

2 komentarze

Mój pracodawca niespodziewanie wpadł na pomysł poddania wszystkich programistów testom algorytmicznym. Plan niepokojący, zwłaszcza dla „seniorów”, wobec których oczekiwania są wysokie, a którzy na co dzień raczej nie implementują własnoręcznie ekstrawaganckich algorytmów sortowania.

Na szczęście (niekoniecznie dla efektów pracy projektowej) w ramach zachęty otrzymaliśmy możliwość uczestnictwa w pięciodniowym kursie algorytmicznym. Mam za sobą dwa takie dni i muszę powiedzieć, że wrócił mi zapał do programowania, jakiego nie czułam od lat!

Urzekł mnie pewien króciutki i bardzo elegancki algorytm rozwiązujący problem znalezienia podciągu o największej sumie.

Problem

Niech dana będzie tablica (ciąg) liczb o długości co najmniej 1.

4 -10 3 29 -3 12 -5 4

Zadanie polega na znalezieniu w tablicy spójnej podtablicy o największej sumie elementów i zwróceniu tej sumy. W naszym przypadku całkowita suma elementów tablicy to 34, natomiast maksymalna suma podciągu elementów to 41. Elementy składające się na tę maksymalną sumę oznaczyłam kolorem czerwonym.

Programujesz?

Poświęć chwilę na rozwiązanie tego problemu. Jaką złożoność obliczeniową ma Twój program?  Brute force to pewnie O(n2). O(nlogn)? Nieźle. Ile masz linii?

Niniejszym przedstawiam przepiękny, pięciolinijkowy algorytm o złożoności liniowej, czyli O(n).

Programowanie dynamiczne

Eleganckie rozwiązanie tego problemu jest oparte na pomyśle określanym mianem „programowania dynamicznego”. Co to znaczy?

Można zauważyć, że niektóre problemy algorytmiczne da się podzielić na mniejsze podzadania.

  • Jeżeli podzadania te są od siebie niezależne, w ramach uproszczenia warto zastosować metodę „dziel i zwyciężaj” – w ten sposób działa wiele dobrych algorytmów sortowania (np. quicksort).
  • Jeśli podzadania w jakiś sposób na siebie nachodzą i jedne wyniki są inkrementacyjnie zależne od drugich, można spróbować użyć programowania dynamicznego.

Programowanie dynamiczne przypomina stosowanie rekurencji, z tą różnicą, że potrzebne nam wyniki cząstkowe wyznaczamy tylko raz. Wynik możemy konstruować wstępująco (najpierw wynik dla najmniejszego podproblemu, potem narastająco dla coraz większych zadań) lub zstępująco (definiujemy „rekurencyjną” zależność pomiędzy wynikiem większego problemu a problemami mniejszymi, tyle że potrzebne nam wyniki zapamiętujemy w jakimś buforze i nie wyznaczamy ich ponownie).

Algorytm Kedane’a

Implementacja w Pythonie dla tablicy A wygląda tak:

I już!!!

Jak to działa?

Najpierw wyznaczamy wynik dla najmniejszej tablicy, o długości jeden. Suma elementów tablicy o tej długości (największa, najmniejsza i każda inna suma) to oczywiście wartość jedynego elementu (A[0]).

Przez cały czas działania algorytmu będziemy utrzymywać dwie zmienne: max_total to nasz najlepszy napotkany do tej pory wynik, natomiast max_local to najlepszy wynik zawierający aktualnie obsługiwany element.

Przechodząc przez kolejne elementy,  za max_local każdorazowo podstawiamy większą z dwóch liczb: aktualny element x lub dotychczasową wartość max_local zwiększoną o x.

Jeśli nowy wynik lokalny jest większy od max_total, zamieniamy wartość max_total.

Ostatnia wartość max_total jest naszą odpowiedzią dla problemu wielkości całej tablicy.

Studium przypadku

Zakresy w tabeli oznaczyłam odpowiednim formatowaniem. Zielone elementy składają się na max_local, a podkreślone na max_total.

Zatem, dla naszej początkowej tablicy, algorytm będzie przebiegał następująco:

Element 0
4
  • max_local = 4
  • max_total = 4
Element 1
4 -10
  • max_local = max(-10,-10+4) = -6
  • max_total = max(4,-6) = 4
Element 2
4 -10 3
  • max_local = max(3,-6+3) = 3
  • max_total = max(4,3) = 4
Element 3
4 -10 3 29
  • max_local = max(29,3+29) = 32
  • max_total = max(4,32) = 32
Element 4
4 -10 3 29 -3
  • max_local = max(-3,32-3) = 29
  • max_total = max(32,29) = 32
Element 5
4 -10 3 29 -3 12
  • max_local = max(12,29+12) = 41
  • max_total = max(32,41) = 41
Element 6
4 -10 3 29 -3 12 -5
  • max_local = max(-5,41-5) = 36
  • max_total = max(41,36) = 41
Element 7
4 -10 3 29 -3 12 -5 4
  • max_local = max(4,36+4) = 40
  • max_total = max(41,40) = 41

Ładny, prawda? 🙂

Posłowia

  1. „Algorytm Kadane’a” piszemy z apostrofem, inaczej niż na przykład „Algorytm Kruskala”. Swego czasu, doprowadzona do ostateczności nadużywaniem apostrofu w polskim Internecie popełniłam wpis na ten temat. W najbliższej przyszłości zamierzam odświeżyć go i opublikować także tutaj, gdyż plaga ta zatacza coraz szersze kręgi.
  2. Pamiętam, że w poprzednim wpisie (Ciągła Integracja: anioł stróż dobrego programisty) obiecałam pokazać, jak stworzyć plan na serwerze Bamboo. Jeszcze chwilka.