Algorytm Kadane 2D – czyli problem maksymalnej dwuwymiarowej podtablicy

Algorytm Kadane w swojej pierwotnej wersji służy do wyszukiwania podciągu o maksymalnej sumie elementów. Biorąc na przykład zwykłą tablicę z jakimiś liczbami jak choćby: 3 -8 9 4 7 6, algorytm Kadane oczywiście znajdzie nam maksymalny podciąg tego ciągu czyli elementy 9, 4, 7, 6 o łącznej sumie 26. Co ciekawe prosta modyfikacja tego algorytmu umożliwi nam wyszukiwanie maksymalnej podtablicy 2D o złożoności  czasowej O((max(x,y))3) gdzie x,y to odpowiednio liczba wierszy i kolumn danej tablicy.

Cała sztuczka polega na stworzeniu dodatkowej jednowymiarowej tablicy o długości odpowiadającej liczbie kolumn naszej dwuwymiarowej tablicy na której poszukujemy maksymalnego podciągu. Algorytm Kadane będzie wyszukiwał maksymalny podciąg właśnie na tej jednowymiarowej tablicy, a my będziemy „przekazywać” do niej odpowiednie sumy elementów.

Załóżmy, że mamy dwuwymiarową (5×4) tablicę liczb całkowitych (mogą być również inne np. typu dobule):

8 4 -4 5
9 3 -7 11
1 2 6 14
-10 8 15 -1
2 11 6 4

Oczywiście maksymalna podtablica dla tego przykładu będzie wyglądać tak:

8 4 -4 5
9 3 -7 11
1 2 6 14
-10 8 15 -1
2 11 6 4

Jej suma elementów będzie wynosić 87.

Nasz program aby dojść do tego wyniku stworzył sobie jednowymiarową tablicę (1×4) do której przypisywał poszczególne sumy elementów, i za każdym razem uruchamiał algorytm Kadane tak aby obliczyć maksymalny podciąg danego ciągu:

1. Najpierw do naszej dodatkowej tablicy wstawiliśmy elementy z pierwszego wiersza:

8 4 -4 5

2. Następnie z pierwszego i drugiego:

8 + 9 = 17 4 + 3 = 7 -4 + -7 = -11 5 + 11 = 16

3. Potem z pierwszego, drugiego i trzeciego:

8 + 9 + 1 = 18 4 + 3 + 2 = 9 -4 + -7 + 6 = -5 5 + 11 + 14 = 30

4. Tym sposobem dochodzimy do momentu kiedy mamy sumę elementów z pierwszego, drugiego, trzeciego, czwartego i piątego wiersza:

8 + 9 + 1 + -10 +2 = 10 4 + 3 + 2 + 8 + 11 = 28 -4 + -7 + 6 + 15 + 6 = 16 5 + 11 + 14 + -1 + 4 = 33

5. Jak widać maksymalny podciąg naszej dwuwymiarowej tablicy to wszystkie elementy, które łączne dają: 10 + 28 + 16 + 33 = 87, na tym moglibyśmy skończyć działanie naszego algorytmu ale do końca nie wiemy czy jest to prawdziwy wynik więc liczymy dalej. Teraz będziemy rezygnować z dodawania kolejnych wierszy od góry, czyli do naszej dodatkowej tablicy w tym kroku zapiszemy sumy drugiego, trzeciego, czwartego i piątego wiersza:

9 + 1 + -10 +2 = 2 3 + 2 + 8 + 11 = 24 -7 + 6 + 15 + 6 = 20 11 + 14 + -1 + 4 = 28

6. Następnie przypisujemy sumy elementów z trzeciego, czwartego i piątego wiersza:

 1 + -10 +2 = -7 2 + 8 + 11 = 21 6 + 15 + 6 = 27 14 + -1 + 4 = 17

7. Tym sposobem dochodzimy do mementu kiedy do naszej dodatkowej tablicy przypiszemy tylko elementy z ostatniego wiersza czyli:

2 11 6 4

Jak widać w kolejnych krokach nie udało nam się przekroczyć sumy, którą uzyskaliśmy w kroku 4, tak więc maksymalny podciąg naszej tablicy2D będzie całą tablicą o łącznej sumie elementów wynoszącej 87.

Poniżej znajduje się w pełni działający program z zaimplementowanym algorytmem Kadane dla tablicy 2D napisany w języku Java:

Przeczytaj również

, , , , , ,