Witam mam zadanie które polega na znalezienie podtablicy z maksylna suma elementów.
Wykorzystałem do tego celu Algorytm Kadane 2D. ze strony
http://strefakodera.pl/algorytmy/algorytmy-wyszukiwania/algorytm-kadane-2d-czyli-problem-maksymalnej-dwuwymiarowej-podtablicy
Niestety zwraca mi niepoprawne wyniki. Dla tablicy wejsciowej :
-2 -3 -1
-3 2 1
-1 2 1
Zwraca wynik 2, a powinien 6 bo maksylna podtablica przeciez jest
2 1
2 1
program sumuje tylko "wierszami". CZy moglby mi ktoś pomóc w modyfikacji ?
int find(int **tab,int n,int m){
int tab_tmp[m] ;
int max1 ;
int suma = tab[0][0];
int max2 = suma;
for(int i = 0;i<n;i++) //wiersze
{
for(int w = 0;w<m;w++) tab_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
{
tab_tmp[k] += tab[j][k];
max1 += tab_tmp[k];
if(max1 > max2) {
max2 = max1;
}
}
if(suma<max2)
suma = max2;
}
}
return suma;
}
- Drugie moje pytanie jak w DEV c++ można testować program z podanymi parametrami ? bo na poczatku wprowadzam dane do tablicy i żeby nie powtarzać x-razy tego samego ciągu liczb.