Županijska razina 2017. / Osnovna škola (7. razred) - 2. zadatak

Trener Slaven analizira nastupe svog kluba u zadnjih N odigranih utakmica. U jednoj utakmici klub je mogao pobijediti protivnika (\(W\) – engl. win), odigrati neriješeno s njim (\(D\) – engl. draw) ili izgubiti (\(L\) – engl. loss).

Slaven želi otkriti koliko je najviše uzastopnih mečeva njegov klub bio nepobijeđen, tj. da je ili pobijedio ili odigrao neriješeno s protivnikom. Kako bi niz nepobjedivosti bio što dulji, Slaven može malo i varati te zanemariti najviše jednu utakmicu u kojoj je njegov klub izgubio, a prošlu i sljedeću utakmicu je pobijedio ili odigrao neriješeno. Prvu i posljednju utakmicu u nizu nije moguće zanemariti.

Napiši program koji će za zadane ishode u \(N\) odigranih utakmica odrediti najdulji niz nepobjedivosti na način kako to Slavenu najviše odgovara.

Ulazni podaci

U prvom retku nalazi se prirodan broj \(N\) \((1 \leq N \leq 150)\), broj iz teksta zadatka.

U drugom retku nalazi se niz od \(N\) znakova \((W, D, L)\), ishodi utakmica iz teksta zadatka.

Izlazni podaci

U jednom retku treba ispisati cijeli broj, duljinu najduljeg niza nepobjedivosti.

Bodovanje

U test podacima vrijednima \(21\) bod neće postojati utakmica koja bi se mogla zanemariti.

U test podacima vrijednima \(21\) bod postojat će samo jedna utakmica koja bi se mogla zanemariti.

Primjeri test podataka

Ulaz

14
WWLLLWWLLWWWLL

Izlaz

3

Ulaz

20
LLDWDWWLLDDLLDWWWLLW

Izlaz

5

Ulaz

18
LWWLDDWWWDLWLLWWWW

Izlaz

8

Objašnjenje

Opis trećeg test podatka: Bez brisanja jedne utakmice najdulji niz nepobjedivosti je DDWWWD. Ako obrišemo \(4.\) utakmicu iz niza, tada je najdulji niz WWDDWWWD, a ako obrišemo \(11.\) utakmicu iz niza, tada je najdulji niz nepobjedivosti DDWWWDW.