Witam.
Mając daną tablicę dwuwymiarową liczb całkowitych należy wyznaczyć maksymalną sumę liczb znajdujących się w podtablicy danej tablicy.
Źródło: main.edu.pl/pl/user.phtml?op=showtask&task=pod&con=PAS
Przelatywanie pętlami dla każdej ustalonej wielkości podtablicy po całej tablicy raczej nie ma większego sensu, ze względu na liczbę obliczeń, a tylko to niestety przychodzi mi do głowy :|
Proszę o wskazówkę jak można by to sprytnie ugryźć.
Pierwsza optymalizacja o której możesz pomysleć jest taka, że aby policzyć sumę dla prostokąta większego wystarczy do mniejszego dodać "krawędzie". A żeby policzyć prostokąt przesunięty musisz odjąć krawędzie z jednej strony i dodać z drugiej.
A mi się osobiście zdaje, że rozwiązanie brute-force o złożoności O(n6) wystarczy przy szybkiej implementacji.
@Shalom - to jest trop, jednak... nie potrafię tego przełożyć na kod.
@mnbvcX - hm, w takim razie spróbowałem zrobić to brutalnie, ale (jak zwykle) gdzieś mam błąd i go nie widzę (program daje złe odpowiedzi)... napisałem tak:
UWAGI: (i, j) to jakby współrzędna prawego dolnego wierzchołka prostokąta, a (m, k) to wsp. lewego górnego wierzch.
cin >> tab[0][0];
int max = tab[0][0];
int aktualnie = 0;
for(unsigned short i = 0; i < n; ++i)
{
for(unsigned short j = 0; j < n; ++j)
{
if(i == 0 && j == 0) continue;
cin >> tab[i][j];
for(short k = j; k >= 0; --k)
{
for(short m = i; m >= 0; --m)
{
for(short n = i; n >= m; --n)
{
for(short p = j; p <= k; ++p)
{
aktualnie += tab[n][p];
}
}
if(aktualnie > max) max = aktualnie;
aktualnie = 0;
}
}
}
}
I, jak mam nadzieję widać, zliczać sumy postanowiłem od prawego dolnego wierzch. do lewego górnego.
to da się zrobić w O(N^3) z dodatkową pamięcią [N] albo "w miejscu"
dla przypadku jednowymiarowego wiadomo, że istnieje rozwiązanie liniowe
w dwuwymiarowym mamy tylko O(N^2) przypadków wartych rozważenia
aha, no tak, kto wie to wie, a kto nie to i tak nie wiele mu to pomoże.
Wasze zdrowie, kieliszeczek
kurdę, przypomniało mi się to na skrzyżowaniu i mało brakło a życiem bym przepłacił :)
No cóż, właściwie jestem początkujący i nie wiem, o czym piszesz, dlatego prosiłbym o rozwinięcie tych metod tudzież nakierowanie, gdzie można o nich poczytać.
pomyśl o przypadku jednowymiarowym
masz wektor, szukasz podwektora o maksymalnej sumie
i to się da zrobić w czasie linjowym
#include <stdio.h>
unsigned int licz=0,licz1=0;
int t[95][95]={
{1, 2, 3, 0, 0},
{2, 5, -7, 0, 0},
{1, -3, 4, 0, 0},
{0, 0, 0, 0, 0},
{0, 0, 0, 0, 0}};
int suma(int s, int w1, int k1, int w2, int k2){
int k;
licz1++;
for( ; w1<=w2; w1++)
for(k=k1; k<=k2; k++) {
s+=t[w1][k];
licz++;
}
return s;
}
int brutal(int N){
int w1,w2,k1,k2,sm,s;
sm=t[0][0];
for(w1=0;w1<N;w1++)
for(k1=0;k1<N;k1++)
for(w2=w1;w2<N;w2++)
for(k2=k1;k2<N;k2++)
if((s=suma(0, w1,k1,w2,k2)) > sm)
sm=s;
return sm;
}
int ss(int sm, int * z, int N){
int i,me=0,ms=0;
for(i=0; i<N; i++){
me=me+z[i]>0?me+z[i]:0;
ms=ms>me?ms:me;
}
return sm>ms?sm:ms;
}
int main(){
int N,w1,w2,k,sm;
N=3;
//scanf("%d",&N);
//for(w1=0;w1<N;w1++)
// for(k1=0;k1<N;k1++)
// scanf("%d", &t[w1][k1]);
sm=t[0][0];
for(w1=0; w1<N; w1++){
sm=ss(sm, t[w1], N);
for(w2=w1+1; w2<N; w2++) {
for(k=0; k<N; k++)
t[w1][k] += t[w2][k]; // było t[0][k]
sm=ss(sm, t[w1], N); // było t[0]
}
}
printf("%d\n%d %u %u", sm, N, licz1, licz);
return 0;
}
Wystarczy chyba poprawić funkcję ss, która szuka maksymalnej sumy w wierszu.
int ss(int sm, int * z, int N)
{
int i,me=0,ms=0,max=z[0];
for(i=0; i<N; i++)
{
max=z[i]>max?z[i]:max;
me=me+z[i]>0?me+z[i]:0;
ms=ms>me?ms:me;
}
if(max<=0)
{
return sm>max?sm:max;
}
return sm>ms?sm:ms;
}