Finden Sie die Teilfolge mit der größten Summe der Elemente in einem array
Ich vor kurzem interviewt, die mit einem Unternehmen, und Sie bat mich, schreiben Sie einen Algorithmus, der feststellt, der Teilfolge mit der größten Summe der Elemente in einem array. Die Elemente im array kann auch negativ sein. Gibt es eine O(n) Lösung? Jeder gute Lösungen sehr geschätzt werden.
meinten Sie längste Teilfolge? Auch ist es längste steigt ?
Was meinst du mit "größte subsequance"? -- Oh, OK. Du meinst wohl: hier finden Sie die Teilfolge mit der größten Summe der Elemente.
meinst du längste Sequenz-Nummer, so dass die Summe dieser zahlen ist am größten in ein array?
ja. seine Teilfolge mit der größten Summe der Elemente
Duplikat von stackoverflow.com/questions/1706529/...
Was meinst du mit "größte subsequance"? -- Oh, OK. Du meinst wohl: hier finden Sie die Teilfolge mit der größten Summe der Elemente.
meinst du längste Sequenz-Nummer, so dass die Summe dieser zahlen ist am größten in ein array?
ja. seine Teilfolge mit der größten Summe der Elemente
Duplikat von stackoverflow.com/questions/1706529/...
InformationsquelleAutor brett | 2010-09-17
Du musst angemeldet sein, um einen Kommentar abzugeben.
Wenn Sie möchten, dass die größte Summe von aufeinander folgenden zahlen, die dann so etwas wie dies funktionieren könnte:
Dass ist nur aus der Spitze von meinem Kopf, aber es scheint richtig. (Ignoriert, dass er meint 0 ist die Lösung für das leeren und alle negativen Sätze.)
Edit:
Wenn Sie wollen auch die Reihenfolge, position:
Gibt es vielleicht einen kürzeren Weg, es zu tun. Wieder, es hat die gleichen Annahmen (mindestens eine positive ganze Zahl). Auch, es findet nur die erste, größte Sequenz.
Edit: geändert, um die Verwendung
max_j
(exklusiv) stattmax_len
.D, meine Antwort sehr deutlich beginnt zu sagen, was es ist, zu beantworten. War es das, was seine Interviewer gesucht? Wir werden es nie wissen. Es ist offensichtlich, was er suchte, als er akzeptiert es. (Wenn er wirklich wollte, dass eine Teilfolge mit der größten Summe, die Antwort ist einfach: entfernen Sie alle negativen zahlen.)
Ja, ich weiß, Sie schrieb es für die fortlaufende Nummer. Kann die person, die schrieb, die Frage war nicht klar. Ich mag deine Lösung für die max-Folge-problem.
InformationsquelleAutor Matthew
Wenn du meinst längsten steigenden Teilfolge, siehe codaddict's Antwort.
Wenn Sie auf der anderen Seite bedeuten, dass man die sub-array mit einer maximalen Summe (macht nur Sinn mit negativen Werten), dann gibt es eine elegante, dynamische Programmierung-Stil linear-Zeit-Lösung:
http://en.wikipedia.org/wiki/Maximum_subarray_problem
genau. Sie müssen auch die Aufzeichnung der start - /end-Positionen für die Rücksendung der subarray selbst natürlich auch. +1.
+1 ... das Finden dieser Algorithmus ist eine routine-übung in den meisten intro-CS-Kurse (CS 101 oder CS-102).
gut, da nur Teilfolge mit maximaler Summe benötigt wird, kann es nicht funktionieren wie folgt : 1. Sortieren Sie das array zunächst in absteigender Reihenfolge. 2. halten Sie zum hinzufügen von das erste element, bis Sie auf einen negativen Wert. Ausgabe der Summe bis jetzt und Sie sind fertig....
InformationsquelleAutor Eyal Schneider
Versuchen Sie den folgenden code:
InformationsquelleAutor Shobhit
Ich nehme an, du meinst längsten steigenden Teilfolge.
Gibt es keine
O(n)
Lösung.Eine sehr naive Lösung wäre, um ein Duplikat zu erstellen array, Sortieren es in
O(NlogN)
und dann finden dieLCS
des sortierten array und das original-array, das dauertO(N^2)
.Dort ist auch ein direkter DP-basierte Lösung ähnlich
LCS
ebenfallsO(N^2)
, die Sie sehen können hier.Aber wenn Sie gemeint längste steigende Sequenz (hintereinander). Diese kann getan werden, in
O(N)
.InformationsquelleAutor codaddict
InformationsquelleAutor asim kadav
Kann dieses problem gelöst werden zwei verschiedene Möglichkeiten.
Den ersten Ansatz haben zwei Variablen mit der Bezeichnung
sum
undMaxSum
.Wir halten auf das hinzufügen von Werten die Summe und vergleicht mit der MaxSum, wenn der Wert für die Summe größer ist als die MaxSum - weisen Summe Wert der MaxSum
Wenn während des Prozesses der Wert für die Summe unter 0 sinkt, wir werden zurücksetzen der Summe und starten Sie das hinzufügen neuer Nummer von der nächsten index-Stationen.
Beispiel-code für die oben genannte Lösung ist als unten:
Der zweite Ansatz zur Lösung dieses Problems ist, dass wir gehen durch jedes element in einem array. Wir haben gleich 2 Variablen Summe und MaxSum.
Zunächst vergleichen wir die addition der Summe mit dem nächsten array-element und die Summe selbst. Wer schon mal größer, der Wert wird gespeichert in der variable Summe.
Nächstes vergleichen wir die Werte von Summe und MaxSum und wer hat mehr Wert - wir speichern diesen Wert in der MaxSum variable.
Der Beispielcode ist wie unten erwähnt:
InformationsquelleAutor vran freelancer
Wenn Sie sich Fragen, was ist eine zusammenhängende Teilfolge, für die die Summe maximal ist, ich habe 4 gefunden algos so weit:-
Brute-force: Finden Sie alle möglichen Summen mithilfe von geschachtelten Schleifen und halten die Aktualisierung der maxSum wenn Sie finden, eine Summe größer als in früheren Wert von maxSum. Die Zeit-Komplexität ist O(n^2)
Dynamische Programmierung Lösung: Dies ist eine bemerkenswert elegante Lösung, die ich gefunden auf StackOverflow selbst - https://stackoverflow.com/a/8649869/2461567v -
Time Komplexität : O(n),
Speicherplatz-Komplexität : O(n)
DP ohne memory - Kadane-Algorithmus -https://en.wikipedia.org/wiki/Maximum_subarray_problem -
Time Komplexität : O(n) Speicherplatz-Komplexität : O(1)
Teile und herrsche-Lösung - http://eecs.wsu.edu/~nroy/Kurse/CptS223/notes/MaxSubsequenceSum.pdf
Time Komplexität : O(nlgn)
InformationsquelleAutor whizvids
C-Funktion sieht wie folgt aus:
InformationsquelleAutor snowgoose