(Python) - Sous séquence contiguë

[invite237d5fed]

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.
-----

[kwariz]

Bonjour,

Je suppose que c'est un exo ?

la première chose à faire avant de seulement essayer de commencer à penser à coder est de construire un algorithme, sans ça tu vas vite foncer la tête dans un mur en béton armé très épais.
Donc la première chose à faire est d'essayer de résoudre ce problème à la main (stylo et feuilles recommandés). Comment trouves-tu à la main le sous tableau de plus grande somme ?

PS: c'est un problème très intéressant qui permet de passer en revue aussi bien les implémentations naïves et comment les améliorer pour obtenir un algorithme plus efficace.

[danyvio]

Comme dit kwariz un peu de réflexion :

Je constitue les séquence d'indice 1,1 puis 1,2 puis 1,2.... puis 2,3, 2,4 ........13,13 (pour suivre ton exemple) Chaque fois je calcule la somme, et je ne garde que la séquence rencontrée la plus forte.