OIJ Minusy(min) nie potrafię znaleźć testów powodujących błędy

0

Cześć !
Rozwiązuję zadanie Minusy tak wygląda mój kod:

def main():
    ciag = input()
    max_p = max_now = 0
    poprzedni = False
    for i in range(len(ciag)):
        if ciag[i] == '+':
            if poprzedni:
                if max_p < max_now:
                    max_p = max_now
                max_now = 0
                poprzedni = False
            max_now += 1
        else:
            if poprzedni:
                max_now += 1
                poprzedni = False
            else:
                poprzedni = True
    if max_now > max_p:
        print(max_now)
    else:
        print(max_p)
main()

wszystkie testy podane w Treści przechodzą, problem jest z późniejszymi, mój program dla tamtych testów liczy zawsze zbyt mało plusów, pomoże ktoś znaleźć testy dla których mój program da złą odpowiedź?

3
  1. Dużo prościej byłoby zwyczajnie zrobić two-pass, przy pierwszym przejściu zamieniać minusy parami na plusy a dopiero potem zliczać
  2. Robisz to wszystko zachłannie, a to błąd. Popatrz na przypadek: - - - + Twój algorytm uzna że należy zrobić + - + podczas gdy algorytm optymalny zrobiłby - + +. Nie możesz tutaj zachłannie zakładać że należy zamieniać pierwsze napotkanie 2 minusy na plus.
0

Jedno przejście easy.

0

Problem można zredukować do takiego, ze między każdym segmentem plusów jest nieparzysta liczba minusów, która dodaje (n-1)/2 plusów do lewej lub prawej strony. Po każdym segmencie minusów można policzyć aktualna liczbę uzyskanych plusów i zaktualizować max. Nie ma możliwości, aby w najlepszym ciągu uczestniczyły 2 segmenty plusów, bo jest dziura wynikająca z nieparzystości minusów. Z tego wynika pewna „lokalność” decyzji (nie ma potrzeby powrotów, stosów czy dodatkach tablic), wiec szukałbym rozwiązania liniowego ze stała pamięcią.

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