Sous séquence contigues

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.

Bonjour plard,

Une ifo importante manque dans ton énoncé : comment sont déterminées les "sous-rubriques" comme tu les appelles ?

Tant qu'on ne sait pas cela, il va être difficile de te donner une piste de recherche.

A+

On peut partir du principe qu’il faut tester toutes les sous-listes de toutes les longueurs possibles…

En supposant également qu’on a pas le “droit” d’utiliser des modules “exotiques”, voici (de façon synoptique) l’algo que j’utiliserais*:

* Définition d’une fonction sum_list qui prend en paramètres une liste d’entiers et retourne leur somme.
* Définition de trois variables stockant la somme maximale atteinte, avec les indices de liste correspondants.

* Le cœur du truc*:
** Une première boucle qui itère sur tous les entiers de 1 à longueur_liste_fournie, appelons n cette variable.
** Une deuxième boucle imbriquée dans la première, qui itère sur les (longueur_liste_fournie - n) sous-listes de longueur n, calcule leur somme, et la compare à la somme maximale précédente (penser aux slice pour obtenir les sous-listes).

Voilà, j’ai essayé de ne pas donner du code “tout cuit”…:mouarf:

Salut,

Citation:

---

Envoyé par plard

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.

---

Pourquoi ne pas commencer par lire quelques chapitres du Python tutorial?
list et slice (sous séquence contigue) sont expliqués ici. Pour ce qui est des boucles et des contrôles c'est ici
- W

L'algorithme suggéré par mont29 est O(n**3). Il est possible de l'optimiser en O(n**2) mais il y a mieux: il y a une solution en temps linéaire.

Cela passe par la résolution d'un problème un peu différent: Quelle est le suffixe (=sous-séquence contiguë qui se termine à la fin de la séquence) de somme maximale d'un séquence de longueur n ?
* Pour n = 1, la solution est triviale
* Pour n > 1, la solution peut être calculée en temps constant à partir de la solution pour (n-1)

En résolvant ce problème pour tous les préfixes de la séquence en entrée, on peut ensuite trouver la solution du problème initial.

Avec une implémentation soignée, on arrive à un complexité temporelle en O(n) et spatiale en O(1).