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:

, , , , , ,

  • Pomocny

    Powyższy tok rozumowania, jak i sam kod źródłowy nie jest pozbawiony błędów. Autor skupił się na analizie przypadku tablicy dwuwymiarowej całkowicie pomijając jednowymiarowy. Na miejscu autora skupiłbym się na bezbłędnej implementacji algorytmu Kadane dla tablicy jednowymiarowej jako punktu wyjścia do rozpatrywania tablicy dwuwymiarowej.
    Weźmy tablicę:
    -1 -2 -3
    -1 2 -1
    -1 -1 -1
    Prawidłowa odpowiedź: 2
    Odpowiedź autora kodu: 1
    Dla innej tablicy:
    -1 2 -1
    Prawidłowa odpowiedź: 2
    Odpowiedź autora kodu: 1

    • Coś chyba pomyliłeś:

      Dla tablicy:
      -1 -2 -3
      -1 2 -1
      -1 -1 -1
      Poprawną odpowiedzią jest jest 1 (tylko środkowy element zawierający 2, dodanie każdego innego zmniejsza jego wartość).

      Dla tablicy:
      -1 2 -1
      Tak samo poprawną odpowiedzią jest 1 (nie wiem skąd według cb. miało być 2?).

      • PoNocny

        Kurcze, twoja wypowiedź sugeruje że nie rozumiesz istoty problemu (szukamy podciągu o maksymalnej sumie elementów, interesuje nas jego suma), lub też nie przeczytałeś opisu problemu.
        Poniżej kolejny test (taki do poduszki):
        -1 -2 -3
        -1 2 3
        -1 -1 -1
        Twój wynik: 4
        Prawidłowy wynik: 5

        • To chyba ty nie rozumiesz: „szukamy podciągu o maksymalnej sumie elementów, interesuje nas jego suma” dla tablicy -1 2 -1 jaka jest maksymalna suma elementów? 2, jaki ma być wynik oczywiście 1.