Maison > développement back-end > Tutoriel Python > Utiliser le langage Python pour décrire la somme maximale des sous-séquences continues

Utiliser le langage Python pour décrire la somme maximale des sous-séquences continues

小云云
Libérer: 2017-12-06 10:42:58
original
3857 Les gens l'ont consulté

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
Copier après la connexion


Les résultats en cours d'exécution


maxsum is 5
Copier après la connexion
Copier après la connexion


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__ == &#39;__main__&#39;:
  list_of_num = [1,3,-3,4,-6]
  maxsum = maxSum(list_of_num)
  print "maxsum is: ",maxsum
Copier après la connexion


Résultats d'exécution


maxsum is 5
Copier après la connexion
Copier après la connexion

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

Maîtriser complètement Python

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!

Étiquettes associées:
source:php.cn
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal