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

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(n² ) 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__ == &#39;__main__&#39;:
  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

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!