Menu Zamknij

Podciąg o największej sumie – Algorytm Kadane

     Częstym zadaniem z jakim można spotkać się na rozmowach kwalifikacyjnych jest rozgrzewkowe zadanie polegające na znalezieniu spójnego podciągu w strukturze danych o największej sumie. W tym przypadku musi być to jednowymiarowa tablica, lista lub vector.

     Nasz problem możemy rozwiązać na wiele sposobów, jak i mocno modyfikować nasze ostateczne rozwiązanie. Główną zaletą algorytmu Kadane jest złożoność w jakiej występuje. Gdybyśmy użyli sposobu brutalnego algorytmu (brute force) skończylibyśmy ze złożonością n^3. Nasz główny bohater przez to, że przechodzi po naszej tablicy tylko jeden raz pozwala nam na końcu osiągnąć złożoność tylko na poziomie liniowym.

Programowanie dynamiczne

     Algorytm Kadane jest przykładem programowania dynamicznego. Jest to technika projektowania algorytmów polegająca na rozwiązywaniu podproblemów i zapamiętywaniu ich wyników. W tym sposobie, podobnie jak w metodzie dziel i zwyciężaj, problem dzielony jest na mniejsze podproblemy. Można przyrównać ten sposób do funkcji rekurencyjnej, ale w tym przypadku nie jesteśmy zmuszeni do ponownego obliczania poprzednich danych.

Kod C++

Kod Java

Kod Python

Kod C#

Kod PHP

Kod Javascript

Kod VBA

     Zobacz Kody w całości link

Zobacz Kursy

10h | C++ Kurs Podstawowy Programowania | -22%

X