maksymalna podtablica

0

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;
    }
}
0
  1. Co ma wypisać program gdy wszystkie liczby w tablicy są ujemne?
  2. Jesteś nowy w Javie? Nie trzeba przekazywać do funkcji rozmiaru tablicy, każda tablica tab jest obiektem, jej rozmiar możesz odczytać tak: tab.length.
  3. Algorytm musi mieć poważne błędy, skoro nie radzi sobie z tablicą dwuelementową
[1163110572, 1638416203]
1 1 620281313

a nawet jednoelementową

[842890073]
0

Dziwne liczby w tablicy wzięły się stąd, że zastąpiłem w Twoim programie wpisywanie liczb losowaniem.

0

Zapomniałem scharakteryzować wejścia, którym nie jest tablica a opis zestawu danych o następujących właściwościach:

• Pierwszą podawaną wartością będzie dodatnia liczba całkowita oznaczająca ilość testowanych zestawów danych po której na wejściu pojawią się zestawy danych w ilości równej wczytanej liczbie.
• Każdy zestaw danych obejmuje dodatnią liczbę całkowitą z zakresu od 1 do 215=32768 oznaczającą ilość danych wczytywanego zestawu, po czym po-dawane są dane zestawu w ilości równej wczytanej liczbie.
• Dane każdego zestawu są liczbami całkowitymi z zakresu od −215 do +215.

Dla sytuacji, gdy brak nieujemnej podtablicy, program ma zwracać 0.

0

Baca na ii uj ? ;) termin minął chyba wczoraj ale jakby co pewnie znajdziesz na wydziale kogoś komu się nudzi

0

... a nawet się może zdarzyć jakiś prowadzący zajęcia który potrafi googla używać ...

0

Przenikliwa analiza odnośnie BaCy ; )
Nie zmienia to jednak faktu, iż problem zalazł mi za skórę i za nic nie mogę go rozwiązać pomimo chęci.

mrfiree

0

Wersja bez skalowania, które możesz trywialnie dorobić: największa suma algorytm?
Edit: nie doczytałem. Mój program oblicza maksymalną podtablicę, bez względu na długość. Ale wybranie najkrótszej to tylko rozbudowanie warunku w jednym ifie.

0

Skalowanie dorobione, nie mogę natomiast poradzić sobie z warunkiem na najkrótszą podtablicę i czy w ogóle chcę go umieścić w dobrym miejscu?

public static String test(long[] array) {
        long max = 0;
        int cur = 0;
        int curLeft = 0;
        int maxLeft = 0;
        int maxRight = -1;
        for (int i = 0; i < array.length; i++) {
            long value = (array[i] > 0) ? (array[i] * 3) : (array[i] * 2);;
            if (cur > -value) {
                cur += value;
            } else {
                cur = 0;
                curLeft = i + 1;
            }
            
            if (max < cur) {
                max = cur;
                maxLeft = curLeft;
                maxRight = i;
            } else if(max == cur) {
// tutaj warunek
                }

            }
        }
        return maxLeft + " " + maxRight + " " +max;
    }

Próbowałem opcji z obliczaniem różnic indeksów, ale po całym dniu przygodnego programowania nie potrafię kreatywnie podejść do problemu. Jakaś pomoc?

Edit:
Wstawiając poniższy warunek w miejsce komentarza, program wciąż nie zwraca poprawnych wyników. Już nie mam pomysłów...

if ((maxRight - maxLeft) > (i - curLeft)) {
                    max = cur;
                    maxLeft = curLeft;
                    maxRight = i;
                }
0

Panie Mateuszu - sugeruje przeczytać uważnie warunki zadania i skupić się na przypadkach skrajnych. Tak to już jest w programowaniu, że obsługa tychże skrajnych przypadków które zdarzają się bardzo rzadko zabiera często więcej czasu niż obsługa sytuacji "zwykłych".

0

Eee ... tam trudne. Chyba zapomnial pan, ze tablica ma być nieujemna - a jaka jest skrajna wartoś sumy nieujemnej? Jest tylko jedna skrajna wartość i chyba nie trudno zgadnąć jaka. A ponadto jest pan w grupie dra Lembasa - wiec może pan zapytać.

0

Jak u Lembasa to najlepiej rozwiązanie dać na kartach perforowanych albo w Algolu :D

0
Wibowit napisał(a)

Jak u Lembasa to najlepiej rozwiązanie dać na kartach perforowanych albo w Algolu :D

Bzdura

0

Prześlęczałem kilka dni nad tym programem, ale wciąż nie wiem w jaki sposób obsłużyć warunki brzegowe dla zera. Z algorytmu który wykorzystywałem pierwotnie, powróciłem do modyfikacji algorytmu Kadane. Raz udaje mi się osiągnąć obsługę zera dla najkrótszego podciągu o długości 1 i sumie 0 ale przy podciągach zawierających zero na brzegach przedziałów otrzymuje podciąg zbyt długi (o zbędne zera), innym razem podciągi bez zer na brzegach ale o podciągu o sumie 0 i długości 1 mogę zapomnieć. Proszę o jakieś wskazówki. Ugrzązłem po uszy i nie mogę tego przeskoczyć.

Program nie przechodzi przykładowo dla poniższych testów:

{0 2 0 2 -12 3}
{-1 0}

Zwraca:
0 3 12
1 0 0
A powinien:
1 3 12
1 1 0

public static String Kadane2(long[] array) {

        long max_so_far = 0, max_ending_here = 0;
        int startIndex = 0, endIndex = 0, curIndex = 0;

        for (int i = 0; i < array.length; i++) {
            long value = (array[i] > 0) ? (array[i] * 3) : (array[i] * 2);

            if (0 > (max_ending_here + value)) {
                max_ending_here = 0;
                curIndex = i + 1;
            } else {
                max_ending_here += value;

            }

            if (max_so_far < max_ending_here) {
                max_so_far = max_ending_here;
                startIndex = curIndex;
                endIndex = i;
            } else if (max_so_far == max_ending_here) {
                if ((endIndex - startIndex) > (i - curIndex)) {
                    max_so_far = max_ending_here;
                    startIndex = curIndex;
                    endIndex = i;
                }
            }
        }
        return (startIndex + " " + endIndex + " " + max_so_far);
    }

Z tym warunkiem jest coś nie tak z całą pewnością, ale na pewno to nie wszystko...

 if ((endIndex - startIndex) > (i - curIndex)) {
                    max_so_far = max_ending_here;
                    startIndex = curIndex;
                    endIndex = i;
                }
0

W warunku:
if (0 > (max_ending_here + value)) {
spróbuj dać >= zamiast >.

ATSD:
Jakiego algorytmu Kadane? To w poście powyżej to praktycznie kalka mojego rozwiązania.

Edit:
Jeśli zmienisz warunek jak podałem powyżej to musisz dodatkowo zapamiętać sobie indeks dowolnego zera w tablicy. Jeżeli nie będzie żadnej dodatniej liczby w tablicy (a więc policzony max będzie niedodatni), ale będzie jakieś zero to wypiszesz ten indeks.

0

Bardzo dobrze - ten kierunek !!!

A z innej beczki - algol bylby lepszy niz Java. I dla zajec o ktorych mowa nawet lepszy od C

0
Wibowit napisał(a)

ATSD:
Jakiego algorytmu Kadane? To w poście powyżej to praktycznie kalka mojego rozwiązania.

Algorytm o którym wspomniałem http://en.wikipedia.org/wiki/Maximum_subarray_problem

Ostatecznie, obładowany warunkami algorytm działa jak należy, więc temat uważam za zakończony, chyba że ktoś jest zainteresowany rozwiązaniem.

Dziękuję za pomoc.

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