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

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

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:

2. Następnie z pierwszego i drugiego:

3. Potem z pierwszego, drugiego i trzeciego:

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

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:

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

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

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:

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);
        }
    }
}

Algorytm Kadane, Algorytm Kadane 2D, Java