:~$ newsletter --subscribe
cat ~/artykuly/algorytmy/algorytm-kadane-2d-czyli-problem-maksymalnej-dwuwymiarowej-podtablicy.md

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

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 momentu, 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 tablicy 2D 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:

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 tablicy
                    max1 = 0;

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

                        if(max1 > max2) max2 = max1;
                        if(max1 < 0) max1 = 0;
                    }

                   if(suma<max2)
                    suma = max2;
                }
            }

            System.out.println("Wynik: " + suma);
        }
    }
}
udostępnij: ·
Łukasz Dudziński
Łukasz Dudziński · założyciel i autor
Pasjonat informatyki, a zwłaszcza programowania. Zwariowany maniak na tle nowych technologii oraz komputerów. W wolnych chwilach bloger... więcej-o-mnie →
ls ~/artykuly/powiazane --limit 3
komentarze --count 1
rss dla komentarzy →
janrosek2024-03-22 ·

nawet ja to lepiej wyjasnilem

dodaj-komentarz

Komentarze są moderowane. Podane dane przetwarzamy wyłącznie w celu publikacji komentarza (polityka prywatności).