Informacje o nowych artykułach oraz akcjach edukacyjnych prosto na Twojej skrzynce e-mail!

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):

84-45
93-711
12614
-10815-1
21164

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

84-45
93-711
12614
-10815-1
21164

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:

84-45

2. Następnie z pierwszego i drugiego:

8 + 9 = 174 + 3 = 7-4 + -7 = -115 + 11 = 16

3. Potem z pierwszego, drugiego i trzeciego:

8 + 9 + 1 = 184 + 3 + 2 = 9-4 + -7 + 6 = -55 + 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 = 104 + 3 + 2 + 8 + 11 = 28-4 + -7 + 6 + 15 + 6 = 165 + 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 = 23 + 2 + 8 + 11 = 24-7 + 6 + 15 + 6 = 2011 + 14 + -1 + 4 = 28

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

 1 + -10 +2 = -72 + 8 + 11 = 216 + 15 + 6 = 2714 + -1 + 4 = 17

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

21164

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:

import java.util.Scanner;

public class Source {
    
    public static void main(String[] args) {
        
        Scanner s = new Scanner(System.in);
        
        System.out.println("Podaj liczbę zestawów danych: ");
        int liczbaZestawow = s.nextInt();
        
        
        for(int q = 0;q<liczbaZestawow;q++)
        {
        	
        	System.out.println("Podaj liczbę wierszy: ");
            int n = s.nextInt(); //liczba wierszy
            
            System.out.println("Podaj liczbę kolumn: ");
            int m = s.nextInt(); //liczba kolumn
            
            long[][] tab = new long[n][m]; //wiersz kolumna
            long[] tmp = new long[m]; //wiersz

            System.out.println("Wprowadź elementy tablicy: ");
            
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    tab[i][j] = s.nextLong();
                }
            }
            
            long max1 = 0;
            long max2 = 0;
            long suma = 0;
        
            for(int i = 0;i<n;i++) //wiersze
            {
                for(int w = 0;w<m;w++) tmp[w] = 0; //czyszczenie tmp         
                for(int j=i;j<n;j++) //wiersze
                {
                    //pierwotna wersja algorytmu Kadane dla jednowymiarowej talbicy
                    max1 = 0;

                    for(int k = 0;k<m;k++) //kolumny
                    {    
                        tmp[k] += tab[j][k];
                        max1 += tmp[k];

                        if(max1 > max2) max2 = max1;
                    }

                   if(suma<max2)
                    suma = max2; 
                }
            }   
            
            System.out.println("Wynik: " + suma);
        }
    }
}

Spodobało się?

Jeśli tak, to zarejestruj się do newslettera aby otrzymywać informacje nowych artykułach oraz akcjach edukacyjnych. Gwarantuję 100% satysfakcji i żadnego spamowania!

, , , , , ,

Dodaj komentarz

Komentarze (6)

  • Pomocny pisze:

    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

    • lukas124 pisze:

      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 pisze:

        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

      • lukas124 pisze:

        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.

  • wetorek pisze:

    Algorytm jest błędny i nie działa, proszę się nim nie sugerować.
    Zaimplementujcie Kadane dla jednowymiarowej i rozszerzcie go

Odpowiedz

Twój adres e-mail nie zostanie opublikowany.

Pin It on Pinterest