def plus_grande_somme2(sequence, defaut=float("-inf")): #defaut: valeur de la séquence vide somme=0 meilleure_somme=defaut for val in sequence: somme = max(somme+val, val) meilleure_somme = max(meilleure_somme, somme) return meilleure_somme
def maj(l, next_n=-1, count=0): if next_n == -1: return maj(l, l[0], 0) # Si liste paire et premier element majoritaire, on le retourne sinon on retourne la même fonction sans le premier element if len(l) % 2 == 0: if 2*l.count(l[0]) == len(l): return l[0] else: return maj(l[1:]) for k,n in enumerate(l): """ L'idée c'est qu'on cherche un élément strictement majoritaire. Donc si on parcourt la liste élément par élément en créant une sorte de liste temporaire On regarde dans cette liste temporaire s'il y a un element en majorité, qu'on garde quand on augmente la liste S'il n'y a pas de majorité, ça veut dire qu'il faut qu'il y ait une majorité dans le reste de la liste. Pour le premier element, il est seul dans la liste, donc il est majoritaire, il y en a 1 de plus de le reste. Si on ajoute le deuxieme element -> Si c'est le même alors il est majoritaire avec une majorité de 2 de plus que le rest -> Si c'est pas le même alors il n'est pas majoritaire, et on réduit le décompte. Ici, le compte arrive à 0, et on rappelle la fonction avec le reste de la liste Et ainsi de suite. Si le compte arrive à zéro, alors on renvoie le reste de la liste et on prend le premier élément comme majoritaire car de toute façon dans les éléments précédents, il n'y a pas de majorité absolue, donc ce qui compte, c'est la majorité absolue dans ce qui reste. Exemple : l=[1,2,1,3,2,1,1] On prend "1", qu'on considère majoritaire dans l[:1] avec count = 1 Ensuite on prend 2, différent de la majorité actuelle donc count = 0 dans l[:2]. Comme count = 0, on se fiche de l[:2] finalement, aucune majorité ne s'en dégage. Donc on veut un majorité dans l[2:] Donc on rappelle la fonction avec l[2:] Ca va etre rappelé avec [1,3,2,1,1] puis [2,1,1] puis [1] donc l'élément potentiellement majoritaire est 1. Il est vérifié dans get_maj """ if count == 0: return maj(l[k:], n, 1) elif count != 0 and next_n == n: count += 1 else: count -= 1 if l.count(next_n)*2 >= len(l): return next_n else: return -1"""Quand on a un élément potentiel, on le compte, et on vérifie qu'il est bon"""def get_maj(l): if l.count(maj(l))*2 >= len(l): return maj(l) else: return -1
def maj(l): count = 0 next_n = -1 if len(l) % 2 == 0: if 2*l.count(l[0]) == len(l): return l[0] else: return maj(l[1:]) for n in l: if count == 0: next_n, count = n, 1 elif count != 0 and next_n == n: count += 1 else: count -= 1 if l.count(next_n)*2 >= len(l): return next_n else: return -1