Trouver la somme de la sous-séquence continue maximale est une question d'entretien très classique et ancienne. Dans cet article, nous partagerons avec vous la description de la sous-séquence continue maximale et de la méthode en langage Python.
1. Description du problème
Supposons qu'il existe un tableau (liste en python) [1,3,-3,4,-6,-1], trouvez la plus grande sous-séquence continue dans le tableau de et. Par exemple, dans ce tableau, la somme des plus grandes sous-séquences consécutives est 5, soit 1+3+(-3)+4 = 5
2.O(n2 ) solution
La méthode la plus simple et la plus grossière, la boucle double couche, utilise une somme maximale pour identifier la somme maximale de sous-séquence continue. Ensuite, chaque jugement est mis à jour. Il n'y a pas grand chose à dire, il suffit d'aller voir le code
def maxSum(list): maxsum = list[0] for i in range(len(list)): maxtmp = 0 for j in range(i,len(list)): maxtmp += list[j] if maxtmp > maxsum: maxsum = maxtmp return maxsum if __name__ == '__main__': list = [1,3,-3,4,-6] maxsum = maxSum(list) print "maxsum is",maxsum
Les résultats en cours d'exécution
maxsum is 5
Solution 3.O(n)
Des exemples de recherche de la somme maximale de sous-séquences consécutives peuvent être trouvés partout où les spécifications dynamiques sont discutées. Plus précisément, supposons que le tableau soit a[i], car la somme continue maximale des sous-séquences doit se terminer quelque part entre les positions 0-(n-1). Ensuite, lorsque la boucle atteint la i-ème position, si la somme des sous-séquences consécutives précédentes est inférieure ou égale à 0, alors la somme maximale des sous-séquences consécutives se terminant à la position i est la valeur de la i-ème position, qui est un[i]. Si la somme des sous-séquences consécutives précédentes est supérieure à 0, la somme maximale des sous-séquences consécutives se terminant à la position i est b[i] = max{ b[i-1]+a[i], a[i]}, où b [i] fait référence à la somme de la plus grande sous-séquence continue.
def maxSum(list_of_nums): maxsum = 0 maxtmp = 0 for i in range(len(list_of_nums)): if maxtmp <= 0: maxtmp = list_of_nums[i] else: maxtmp += list_of_nums[i] if(maxtmp > maxsum): maxsum = maxtmp return maxsum if __name__ == '__main__': list_of_num = [1,3,-3,4,-6] maxsum = maxSum(list_of_num) print "maxsum is: ",maxsum
Résultats d'exécution
maxsum is 5
Ce qui précède est Utilisez le langage Python pour décrire la sous-séquence continue maximale et le didacticiel, j'espère que cela pourra aider tout le monde.
Recommandations associées :
Sous-séquence et problème continus maximaux
Introduction à la version python du modèle d'usine simple
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!