Witam. Mam problem z zadaniem o następującej treści:
*Dla danej niepustej tablicy dwuwymiarowej liczb całkowitych: a[0][0], … ,a[n-1][m-1] dla
0 ≤ i ≤ j < n, 0 ≤ k ≤ l < m definiujemy jej maksymalną podtablicę jako spójny jej fragment
a[i .. j][k .. l] o maksymalnej nieujemnej sumie elementów, obliczanej według
wzoru: s(i, j, k, l) = suma elementów a[x][y] tej tablicy, dla których i ≤ x ≤ j oraz k ≤ y ≤ l.
W przypadku gdy wszystkie liczby tablicy są ujemne, maksymalna podtablica jest pusta
i s(i, j, k, l) jest równa 0.
Napisz w Javie program działający w czasie O((max(n, m))^3), który wyznacza
maksymalną podtablicę a[i .. j][k .. l] i jej maksymalną wartość s(i, j, k, l). **Przy czym podtablica
a[i .. j][k .. l] zawiera najmniejszą liczbę elementów, której indeksy i, j, k, l tworzą ciąg
leksykograficznie najmniejszy. ** *
Samo wyznaczenie maksymalnej sumy nie jest zbyt trudne i najsensowniejszy jest algorytm Kadane, zatem ten algorytm zaimplementowałem. Natomiast mam duży problem z samymi indeksami podtablicy... Często program wyznacza poprawną sumę, ale samych podtablic z taką sumą jest kilka i program nie wybiera odpowiedniej (o najmniejszej liczbie elementów i której indeksy tworzą ciąg leksykograficznie najmniejszy). Nie bardzo wiem, jak "wzbogacić" algorytm kadane dla 2d, aby program spełniał dodatkowe wymogi...
Poniżej wklejam swój kod:
import java.util.Scanner;
public class Source3 {
public static Scanner in = new Scanner(System.in);
public static void main (String[] args)
{
int zestaw = in.nextInt();
for(int z=1; z<=zestaw;z++) {
int m = in.nextInt();
int n = in.nextInt();
int [][]matrix = new int[m][n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
matrix[i][j]=in.nextInt();
}
}
maxSubarray(matrix,m,n);
}
}
public static void maxSubarray(int a[][],int m, int n){
int i;
int j;
int g;
int h;
int t;
int prev=0;
int M=0;
int r1=0;
int r2=0;
int c1=0;
int c2=0;
int[] p=new int[n];
for (g = 0; g < m; g++) {
for (j = 0; j < n; j++) {
p[j] = 0;
}
for (i = g; i < m; i++) {
t = 0;
h = 0;
for (j = 0; j < n; j++) {
p[j] = p[j] + a[i][j];
t = t + p[j];
if (t < 0) {
t = 0;
h = j + 1;
}
if (t > M) {
M = t;
r1 = g;
c1 = h;
r2 = i;
c2 = j;
}
}
}
}
System.out.println("max_sum= "+M +", "+"a[" + r1 + ".." + r2 + "]" + "[" + c1 + ".." + c2 + "]");
}
}
Dołączam również przykładowy test jak to powinno wyglądać:
input:
5 //ilosc zestawow
2 5 //il. wierszy, il. kolumn
1 1 -1 -1 0
1 1 -1 -1 4
2 5
0 -1 -1 1 1
4 -2 -2 1 1
2 5
0 -1 -1 4 0
4 -2 -2 0 0
2 5
-1 -2 -3 -1 -2
-1 -1 -1 -1 -5
1 6
-2 7 -4 8 -5 4
output:
max_sum = 4, a[1..1][4..4]
max_sum = 4, a[1..1][0..0]
max_sum = 4, a[0..0][3..3]
empty
max_sum = 11, a[0..0][1..3]
U mnie output wygląda natomiast tak:
max_sum= 4, a[0..1][0..1]
max_sum= 4, a[0..1][0..0]
max_sum= 4, a[0..0][3..3]
max_sum= 0, a[0..0][0..0]
max_sum= 11, a[0..0][1..3]
Z góry dziękuję za jakąkolwiek pomoc.