Schön, Sie alle kennenzulernen. Ich heiße ryuichi69.
Heute werde ich die Ausgabe dessen schreiben, was ich hier mit dem Algorithmus studiert habe. Heute haben wir es mit einem Algorithmus zu tun, der als maximales Subarray-Problem bezeichnet wird. Bitte teilen Sie uns in den Kommentaren mit, ob Teile schwer verständlich sind oder Anforderungen fehlen.
Was ist das maximale Subarray-Problem?
Nun, das ist das Hauptthema. Das Problem der maximalen Teilsumme ist ein Problem, das besagt: " In jedem Element befindet sich ein Array mit Ganzzahlen. Wenn Sie einige davon auswählen, ermitteln Sie den Maximalwert der Summe der ausgewählten ".
Problem
Sei
n eine ganze Zahl größer oder gleich 0. Zu diesem Zeitpunkt erfüllt die aus n Elementen bestehende Zahlenfolge (Array) a [k] die folgenden Bedingungen.
Außerdem sei k eine natürliche Zahl, die 1 ≤ k ≤ n erfüllt. Wählen Sie k Elemente aus der Sequenz a [n] aus. Erstellen Sie ein Programm, in dem die Summe der zu diesem Zeitpunkt ausgewählten Elemente S [k] ist.
* Da dies eine Algorithmuspraxis ist, berücksichtigen wir den Rechenaufwand nicht.
a = [7,9,-1,1,-4]
k = 4
* Wenn a = [7,9, -1,1] und die Elemente des Arrays nicht wie oben beschrieben in absteigender Reihenfolge sind, sortieren Sie die Elemente des Arrays in absteigender Reihenfolge und insgesamt.
17
a = [-1,-2,-3,-4]
k = 3
* Wenn alle Elemente negative Ganzzahlen sind, werden sie nicht hinzugefügt.
0
-Sequenz in der Reihenfolge von 0 hinzu. Und wenn die Gesamtwertschöpfung größer ist als vor der Addition, wird dieser Wert als S_k übernommen. Insbesondere
Recommended Posts
Python-Programm
solve.php
# a[i]Jedes Element von anordnen
#Bubble sortiert das Array einmal
def bsort(arr):
#Zum Ersetzen
temp = 0
#Doppelschleife{Der Berechnungsbetrag beträgt O.(n^2)}
for i in range(0,len(arr)-1):
for j in range(0,len(arr)-1):
#Dieses Mal ist es in absteigender Reihenfolge, sodass das nächste Element vom aktuellen Element stammt
#Nur wenn es groß ist, wird es ersetzt.
if(arr[j] < arr[j+1]):
temp = arr[j]
arr[j] = arr[j+1]
arr[j+1] = temp
return arr
#Zwei ganze Zahlen a,Gibt das größere von b zurück
def max(a,b):
if a > b:
return a
return b
def solve(arr,k):
#Sortieren Sie zuerst das Array in absteigender Reihenfolge
b = bsort(arr)
#Dynamische Planungsmethode(dp)Notieren Sie sich den Gesamtwert jeder Stufe
dp = [0] * len(arr)
#Berechne dp{Der Berechnungsbetrag beträgt O.(n)}
for i in range(0,len(b)):
# dp[0](UrsprünglicherWert)Zu entscheiden
if i == 0:
#B, wenn die Elemente des Arrays Ganzzahlen größer als 0 sind[0]
#Dp 0, wenn die Elemente des Arrays Ganzzahlen kleiner als 0 sind[0]Adoptieren zu
#Da es in absteigender Reihenfolge nach Blasensortierung sortiert ist, b[0] <Wenn 0
#Danach alle Summe dp[i]Wird 0 sein
dp[0] = max(b[0],0)
else:
# dp[i-1]+b[i]>dp[i-1]Nur bei dp[i]Angenommen für
#Ansonsten dp[i-1]Dp[i]Angenommen für
#Es tut mir Leid. Korrigiert(2019.12.29)
dp[i] = max(dp[i-1]+b[i],dp[i-1])
#Dp entspricht dem zweiten Argument[k]Gib es zurück
return dp[k-1]
#zum Test
if __name__ == "__main__":
a = [7,9,-1,1,-4]
print(solve(a,4))
b = [-1,-2,-3,-4]
print(solve(b,3))
Referenz
Ark's Blog | Kadane’s Algorithm |Maximales Teilarray-Problem
Qiita | Algorithmus und Datenstruktur in C # 1 ~ Maximales partielles Array-Problem ~