Najdluzszy spojny podciag o sumie 4

Question

Witam!

Jak w temacie. Niestety wgl nie mam pomyslu jak sie do tego zabrac.

Ogolnie zadanko łatwe gdyby nie liczby ujemne.

Dla przykladu:

3 -2 6 1 -1 5

wynik = 4

Jest tak bo mamy dwa spojne podciagi o sumie 4:

-2 6

-2 6 1 -1

ale najdluszy ma dlugosc 4 (nasz wynik)

Mialem pomysl zeby zrobic sumy prefiksowe ale dalej nie mam pojecia co z nimi zrobic ;/

Answer 1

Nie wiem, czy mój algorytm jest najoptymalniejszy, bo wymyśliłem go na szybko, ale powinien rozwiązać zadanie. Otóż:

1. Posiadasz zmienną oznaczającą długość najdłuższego podciągu o sumie 4. Na początku niech posiada neutralną wartość -1, czyli brak podciągu.
2. Zaczynasz sprawdzać sumę liczb od pierwszej, sukcesywnie dodając kolejne. Gdy dojdziesz do sumy równej 4, sprawdzasz, czy długość aktualnego podciągu jest większa od długości maksymalnej. Jeśli tak, aktualizujesz wartość, jeśli nie, pomijasz tę czynność.
3. Gdy zsumujesz wszystkie liczby ciągu (od pierwszej do ostatniej), zaczynasz dodawanie od drugiej i znowu idziesz do końca.
4. Algorytm kończy się, gdy obliczysz i sprawdzisz wartość ostatniej liczby (podciąg jednoelementowy).

Oto prosty pseudokod:

maxLength = -1;
for i = 0; i < N; i++
do
    sum = 0;

    for j = i; j < N; j++
    do
        if i != j
        then
            sum = sum + numbers[j];
        elseif i == j
        then
            sum = numbers[j];
        end

        actualLength = j - i + 1;
        if sum == 4 and actualLength > maxLength
        then
            maxLength = actualLength;
        end
    end
end

Comments

Dzieki, ale jest to złozonosc n kwadrat

A zaley mi na zlozonosci w granicach n do nlong ;/

Tak na bruta to tez potrafie zrobic ;p