(Python) Sous séquence contigues Fermé

Question

Bonjour,

je dois écrire un script Python qui, à l'aide des fonction Liste, boucle for et itérateur range(), et à partir d'une liste non trié d'entiers qu'un utilisateur du programme fournira, affiche la somme maximale d'une sous séquence contiguë présente dans la liste. De plus, je dois retourner les indices du début et de la fin de la sous séquence dans la liste. Les éléments de la liste peuvent être positifs ou négatifs. Par exemple si la liste contient les éléments suivants : 11, 13, -4, 3, -26, 7, -13, 25, -2, 17, 5, -8, 1
La sous séquence 3, -26, 7, -13, 25 a pour somme -4, par contre, la sous séquence de somme maximale est 25, -2, 17, 5 (de somme 45). Votre script devra afficher par conséquence : 45 7 10.

J'aimerais si possible que quelqu'un m'éclair sur ce problème car c'est la folie je ne sais pas par ou commencer.
Merci d'avance.

Utilisateur anonyme · Answer

Bonjour

Si on ne t'impose pas de prendre une méthode optimale, tu peux énumérer tous les cas.
il y a N sous-listes qui commencent par le 1er nombre (le nombre seul, les deux premiers nombres... jusqu'à la liste complète)
il y a N-1 sous-listes qui commencent par le 2ème nombre
...
il y a 1 seule sous-liste qui commence par le dernier nombre

Il y a donc en tout N + (N+1) + (N+2) ... +1 sous-listes
Soit N (N+1)/2, ce qui n'est pas grand chose.
Je ne sais pas  l'écrire en python, mais il doit suffire de deux boucle imbriquées.

(Python) Sous séquence contigues

1 réponse

Discussions similaires