Algorytym Kadane 2D

0

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; 

}
  1. 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.

  2. I dlaczego ta funkcja nie działa w VS 2013 ? kompilator wywala błąd już na linijce

int tab_tmp[m] ; 
1
  1. I dlaczego ta funkcja nie działa w VS 2013 ? kompilator wywala błąd już na linijce
int tab_tmp[m] ; 

int tab_tmp[m] ; <- m musi być stałą (const) , jeśli chcesz zrobić dynamiczną tablicę to użyj wskaźników
np.
int *tab_tmp;
tab_tmp = new int [m];

0

Po pierwsze, max1, max2 i suma musi być wyzerowane:

<ort> max1 = 0;
max2 = 0;
suma = 0;</ort>

Po drugie masz dokładnie opisane jak działa ten program więc czego nie rozumiesz? Całość działa na wierszach bo tak funkcjonuje algorytm kadane w pierwotnej wersji dla tablic 1 wymiarowych.

1 użytkowników online, w tym zalogowanych: 0, gości: 1