[Java] pierwsza najkrótsza, maksymalna, nieujemna podtablica

[mrfiree]

Witam wszystkich,
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;
    }

[pfauel]

cześć,
przyjrzałem się Twojemu kodowi i wygląda całkiem nieźle. W jakiej dokładnie sytuacji zwraca on błędny wynik?

Jedyne co mi się podejrzane wydaje (jeżeli to wszystko dobrze zrozumiałem ) w Twoim kodzie to to, że zawsze dla max1 == 0 na koniec zwracasz "0". Przecież max1 == 0 otrzymasz również dla wejścia {-2, 0} przykładowo, a w tej tablicy istnieje przecież podtablica z nieujemną sumą elementów - {0} ((indeks pierwszego elementu = 1) (ostatniego elementu = 1) (suma obliczana ze wzoru 3*dodatnie+2*ujemne = 0)). To samo tyczy się oczywiście sytuacji jak masz na wejściu po prostu tablice jednoelementową {0}.

Żeby tą sytuacje wyłapać dodałbym po prostu zmienną flagową:

Kod: Zaznacz cały

public static String maxArrayN(long[] array) {
        int b1 = 0, e1 = 0;
        int b2 = 0;
        long max1 = 0;
        long max2 = 0;
        int lenght = array.length;
        boolean flag = false;
        for (int i = 0; i < array.length; i++) {
            long temp;
            if (array[i] < 0) {
                temp = array[i] * 2;
            } else {
                temp = array[i] * 3;
            }
            if(temp == 0)			
                flag = true;
            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 && !flag) ? "0" : b1 + " " + e1 + " " + max1;
    }

Mam nadzieję, że niczego nie pomieszałem.
pozdrawiam