Verwenden Sie die Python-Sprache, um die maximale kontinuierliche Teilsequenzsumme zu beschreiben

Das Ermitteln der Summe der maximal kontinuierlichen Teilsequenz ist eine sehr klassische und alte Interviewfrage. In diesem Artikel werden wir die Beschreibung der maximal kontinuierlichen Teilsequenz und die Methode in der Python-Sprache mit Ihnen teilen.

1. Problembeschreibung

Angenommen, es gibt ein Array (Liste in Python) [1,3,-3,4,-6,-1], finden Sie die größte kontinuierliche Teilsequenz im Reihe von und. In diesem Array beträgt beispielsweise die Summe der größten aufeinanderfolgenden Teilsequenzen 5, d. h. 1+3+(-3)+4 = 5

2.O(n² ) Lösung

Der einfachste und gröbste Weg, eine Doppelschichtschleife, verwendet eine Maximalsumme, um die maximale kontinuierliche Teilsequenzsumme zu identifizieren. Dann wird das Urteil jedes Mal aktualisiert. Es gibt nicht viel zu sagen, gehen Sie einfach zum 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

Die Laufergebnisse

maxsum is 5

3.O(n)-Lösung

Beispiele für die Ermittlung der maximalen Summe aufeinanderfolgender Teilfolgen finden sich überall dort, wo dynamische Spezifikationen besprochen werden. Nehmen Sie insbesondere an, dass das Array a[i] ist, da die maximale kontinuierliche Summe von Teilsequenzen irgendwo zwischen den Positionen 0-(n-1) enden muss. Wenn die Schleife dann zur i-ten Position durchläuft und die Summe der vorherigen aufeinanderfolgenden Teilsequenzen kleiner oder gleich 0 ist, dann ist die maximale Summe aufeinanderfolgender Teilsequenzen, die an Position i enden, der Wert der i-ten Position. Das ist ein[i]. Wenn die Summe der vorhergehenden aufeinanderfolgenden Teilsequenzen größer als 0 ist, ist die maximale Summe aufeinanderfolgender Teilsequenzen, die an Position i enden, b[i] = max{ b[i-1]+a[i], a[i]}, wobei b [i] bezieht sich auf die Summe der größten kontinuierlichen Teilfolge.

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

Laufergebnisse

maxsum is 5

Das Obige ist Verwenden Sie die Python-Sprache, um die maximale kontinuierliche Teilsequenz und das Tutorial zu beschreiben. Ich hoffe, es kann jedem helfen.

Verwandte Empfehlungen:

Maximal kontinuierliche Teilsequenz und Problem

Python vollständig beherrschen

Einführung in die Python-Version des einfachen Factory-Musters

Das obige ist der detaillierte Inhalt vonVerwenden Sie die Python-Sprache, um die maximale kontinuierliche Teilsequenzsumme zu beschreiben. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!