[Algorytmy] Tablica dwuwymiarowa- maksymalna suma podtablicy

[cyberciq]

Myślę, że jest to dosyć znane zadanie. Mamy sobie tablicę dwuwymiarową liczb całkowitych. Zadaniem programu jest wypisać maksymalną sumę liczb spójnej prostokątnej podtablicy zawartej w naszej tablicy. Jeśli tablica jest wypełniona tylko dodatnimi lub tyko ujemnymi liczbami to rezultat jest trywialny. Jeśli jednak mamy pomieszane liczby dodatnie i ujemne to pierwsze rozwiązanie, które od razu nasuwa się na myśl jest takie, że bierzemy sobie jakiś "róg" danej tablicy i za pomocą pętli znajdujemy wszystkie możliwe podtablice, których dany wierzchołek jest odpowiednio w tym wierzchołku powtarzając dla pozostałych pól,podtablice sumujemy i porównując otrzymujemy szukaną wartość. Oczywiście taki algorytm działa wolno dla dużych danych więc jeśli ktoś ma jakieś pomysły jak zoptymalizować jego działanie lub wymyślić coś innego to proszę aby się nim podzielił.

pozdrawiam

[argv]

Całkiem niezłe rezultaty daje zastosowanie sum prefiksowych. Założe, że tablica jest kwadratowa. O sumach prefiksowych w tablicy 2d możesz poczytać w książeczce do 8 oi (zadanie Mapa Gęstości).

Kod: Zaznacz cały

for ( i = 1; i <= n; i++) {    for ( j = 1; j <= n; j++) {            wczytaj(sum[i][j]) ;            sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + sum[i][j] ;    }}  

No i teraz 4 pętle:

Kod: Zaznacz cały

int max_sum(int n){    int temp;    int max = -INF ;    for(int i = 1; i <= n; i++)    for(int j = 1; j <= n; j++)        // Podprostokąt zaczynający się w (p,q)        for(int p = i; p <= n; p++)        for(int q = j; q<= n; q++) {            temp = sum[p][q] - sum[p][j-1] - sum[i-1][q] + sum[i-1][j-1] ;            if (temp > max)                max = temp ;        }        return max ;}  

Przechodzi testy na UVa Online Judge (to chyba stamtąd robiłem to zadanie). Istnieje lepszy algorytm, ale skoro ten działał dość szybko i był prosty, to nie chciało mi się tamtego zgłębiać.

[adambak]

argv, to drugie rozwiązanie pewnie opiera się o drzewo przedziałowe?

[Zordon]

Z tego co widzę to powyższe jest \(\displaystyle{ O(n^4)}\), już dużo lepiej niż brutalnie, ale można poprawić do \(\displaystyle{ O(n^3)}\) i algorytm wciąż będzie bardzo prosty.
Robimy sobie powiedzmy sumy prefiksowe dla każdej kolumny: \(\displaystyle{ s[i{}][j]=t[0][j]+t[1][j]...+t[i-1][j]}\), to dosyć łatwo wyliczyć w \(\displaystyle{ O(n^2)}\). Teraz mogę liczyć takie sumy: \(\displaystyle{ t[k][j]+t[k+1][j]...+t[l][j]}\) w czasie \(\displaystyle{ O(1)}\) (dla dowolnych \(\displaystyle{ k,l,j}\)).
Dzięki temu możemy dla każdego poziomego paska (taki pasek to wiersze od pozycji \(\displaystyle{ p}\) aż do \(\displaystyle{ q}\)) rozwiązać problem dla jednowymiarowej tablicy (maksymalna suma podtablicy). Czyli złożoność to \(\displaystyle{ O(n^2 \cdot T(n))}\) gdzie \(\displaystyle{ T(n)}\) to koszt rozwiązania problemu w wersji 1-wymiarowej, który jest liniowy. Polecam wymyślić samemu.

edit: chyba da się też zrobić to w czasie \(\displaystyle{ O(n^2\cdot p(\log n))}\) gdzie \(\displaystyle{ p}\) jest wielomianem, chyba kwadratowym. W praktyce raczej zadziała to nawet wolniej.

[Xitami]

... okata_main