Flip a coin! – Regional event 2021

Level 3

Énoncé

Un des jeux les plus connus chez les dieux grecs du concours Prologin est le "flip a coin!". Imaginez une rangée de pièces alignées, posées soit sur le côté face, soit sur le côté pile, de façon aléatoire ; le but de ce jeu est de calculer la longueur maximale d'une séquence de pièces dont le côté face est visible, en considérant qu'on peut retourner une des pièces de la rangée pour voir son côté face. Attention, on ne peut retourner qu’une pièce, il est impossible d'en retourner plus ou de changer l'ordre des pièces !

Le dieu Valonysos qui se fait toujours battre par les autres décide de se poser un jour, et de réfléchir au problème une bonne fois pour toutes, afin d'établir une méthode pour gagner rapidement et le plus souvent possible.

Aidez Valonysos à trouver un algorithme capable de résoudre son problème à tous les coups, pour qu'il soit certain de gagner la prochaine fois !

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : nombre_de_pieces, le nombre de pièces dans le jeu.
  • Sur la ligne suivante, une liste nombre_de_pieces de caractères juxtaposés : rangee_de_pieces, description de la rangée de pièces dans le jeu.

Sortie

Afficher la longueur maximale de la séquence de pièces côté face que l'on puisse obtenir.

Contraintes

  • $1 \le \text{nombre_de_pieces} \le 100$

Runtime constraints

Maximum memory usage
1000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
3
PPP
Sample output
1
Note

Ici, on retourne n'importe quelle piece et on obtient une sequence de 1 face au maximum.

Sample input
3
FPF
Sample output
3
Note

Ici, il faut retourner la pièce qui se trouve entre les deux face pour obtenir une séquence de longueur 3 !

Submit your solution

You have to register or log in to be able to submit your solution.