Mam problem z algorytmem wyznaczającym pierwszą, najkrótszą, maksymalną, nieujemną podtablicę w czasie liniowym. Wyniki jakie otrzymuję nie są poprawne dla pewnych testów automatycznych. Siedzę od kilku godzin stosując różne techniki wykrywania błędów i wciąż nie wiem co jest nie tak. Będę wdzięczny za każdą możliwą pomoc, choćby podanie suchego algorytmu bez patrzenia na mój kod.
Wejście:
liczba zestawów
liczba elementów w zestawie
dane zestawu
Wyjście:
(indeks pierwszego elementu) (ostatniego elementu) (suma obliczana ze wzoru 3*dodatnie+2*ujemne)
Kod: Zaznacz cały
public static String maxArrayN(long[] array, int nElem) {
int b1 = 0, e1 = 0;
int b2 = 0;
long max1 = 0;
long max2 = 0;
int lenght = nElem;
for (int i = 0; i < nElem; i++) {
long temp;
if (array[i] < 0) {
temp = array[i] * 2;
} else {
temp = array[i] * 3;
}
max2 = max2 + temp;
if (max2 < 0) {
max2 = 0;
b2 = i + 1;
} else if (max2 > max1) {
max1 = max2;
b1 = b2;
e1 = i;
lenght = e1-b1;
} else if (max2 == max1) {
int lenght2 = i-b2;
if(lenght2<lenght) {
max1 = max2;
b1 = b2;
e1 = i;
lenght=lenght2;
}
}
}
return (max1 == 0) ? "0" : b1 + " " + e1 + " " + max1;
}