Hej,
To mój pierwszy post, więc witam wszystkich użytkowników 4programmers.
Zmagam się z zadaniem napisania w czasie liniowym algorytmu wyznaczającego pierwszą najkrótszą maksymalną nieujemną podtablicę, gdzie suma obliczana jest ze wzoru 3dodatnie+2ujemne. Na wyjściu wymagane są: indeks pierwszego elemenu, indeks ostatniego elementu oraz suma podtablicy.
Patrząc na kod, nie widzę żadnych błędów a mimo to wyniki jakie otrzymuję nie są poprawne.
public class Source {
public static Scanner inputScanner = new Scanner(System.in);
public static void main(String[] args) {
int packageNo = inputScanner.nextInt();
for (int i = 0; i < packageNo; i++) {
int number = inputScanner.nextInt();
long[] array = new long[number];
for (int j = 0; j < number; j++) {
array[j] = inputScanner.nextLong();
}
System.out.println(maxArrayN(array, number));
}
}
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;
}
}