Comme vous le savez sûrement, il existe souvent des approches plus efficaces que l’approche par force brute. Proposez un algorithme paire_max_efficace qui résout le même problème que paire_max mais qui présente une complexité temporelle inférieure. Pour vous aider, vous pourriez commencer par imaginer la recherche de l’élément maximal et voir comment l’adapter à la recherche d’une paire de somme maximale. Attention, il vous est interdit d’utiliser un algorithme de tri.
Vous êtes chargés d'implémenter la fonction suivante en Python.
Pour préparer votre code, vous pouvez télécharger le fichier paire_max_efficace.py qui contient la signature de la fonction et quelques exemples de tests.
Attention : seul le résultat renvoyé est évalué et non la complexité temporelle.
Note: Lorsqu'il vous est demandé d'implémenter une fonction, vous êtes invités à ne remplir que le corps de la fonction à implémenter.
def paire_max_efficace(a):
"""
Calcule la somme maximale d'une paire d'entiers de `a`
pre: `a` est un tableau (list) d'entiers
pre: len(`a`) >= 2
post: retourne la somme maximale obtenue à partir d'une
paire d'entiers de `a`
"""