Eine Teilsequenz ist eine Sequenz, die durch Löschen einiger Elemente aus einer anderen Sequenz abgeleitet werden kann, ohne die Reihenfolge der verbleibenden Elemente zu ändern. Eine streng ansteigende Teilfolge ist eine Teilfolge, bei der jedes Element größer als das vorhergehende ist.
Die am stärksten zunehmende Teilsequenz einer Sequenz ist die streng zunehmende Teilsequenz mit der größten Elementsumme.
Implementieren Sie ein Programm oder eine Funktion in der Sprache Ihrer Wahl, die die Elementsumme der am stärksten ansteigenden Teilsequenz einer bestimmten Liste nicht negativer Ganzzahlen ermittelt.
Beispiele:
[] -> 0 ([])
[3] -> 3 ([3])
[3, 2, 1] -> 3 ([3])
[3, 2, 5, 6] -> 14 ([3, 5, 6])
[9, 3, 2, 1, 4] -> 9 ([9])
[3, 4, 1, 4, 1] -> 7 ([3, 4])
[9, 1, 2, 3, 4] -> 10 ([1, 2, 3, 4])
[1, 2, 4, 3, 4] -> 10 ([1, 2, 3, 4])
[9, 1, 2, 3, 4, 5, 10] -> 25 ([1, 2, 3, 4, 5, 10])
[3, 2, 1, 2, 3] -> 6 ([1, 2, 3])
Beachten Sie, dass Sie nur die Elementsumme der am stärksten ansteigenden Teilsequenz angeben müssen, nicht die Teilsequenz selbst.
Der asymptotisch schnellste Code gewinnt mit einer kleineren Codegröße in Bytes als Tiebreaker.
Antworten:
Javascript (ES6)
O(n log n)
253 ZeichenDies verwendet Fenwick-Bäume (einen maximalen Fenwick-Baum), um Maxima bestimmter Teilsequenzen zu finden.
Grundsätzlich wird im zugrunde liegenden Array des Datentyps jede Stelle mit einem Element aus der Eingabeliste in derselben Reihenfolge abgeglichen. Der Fenwick-Baum wird überall mit 0 initialisiert.
Vom kleinsten zum größten nehmen wir ein Element aus der Eingabeliste und suchen nach dem Maximum der Elemente links. Sie sind die Elemente, die in der Teilsequenz vor diesem Element stehen können, da sie in der Eingabesequenz links stehen und kleiner sind, weil sie früher in den Baum eingegeben wurden.
Das Maximum, das wir gefunden haben, ist die schwerste Sequenz, die zu diesem Element gelangen kann. Daher addieren wir das Gewicht dieses Elements und setzen es in den Baum.
dann geben wir einfach das Maximum des gesamten Baumes als Ergebnis zurück.
auf Firefox getestet
quelle
Python, O (n log n)
Ich habe das nicht Golf gespielt, weil ich hauptsächlich auf der schnellsten Code-Seite der Dinge konkurriere. Meine Lösung ist die
heaviest_subseq
Funktion, und unten befindet sich auch ein Testkabelbaum.Laufzeitanalyse:
Die Einfügeposition jedes Elements wird einmal nachgeschlagen, einmal eingefügt und möglicherweise einmal gelöscht, zusätzlich zu einer konstanten Anzahl von Wertesuchen pro Schleife. Da ich das integrierte Halbierungspaket und das Blist-Paket verwende , ist jede dieser Operationen
O(log n)
. Somit beträgt die GesamtlaufzeitO(n log n)
.Das Programm verwaltet eine sortierte Liste der bestmöglichen ansteigenden Teilsequenzen, die als Tupel aus Endwert und Sequenzsumme dargestellt werden. Eine zunehmende Teilsequenz befindet sich in dieser Liste, wenn bisher keine anderen Teilsequenzen gefunden wurden, deren Endwert kleiner und die Summe mindestens genauso groß ist. Diese werden in aufsteigender Reihenfolge des Endwertes und notwendigerweise auch in aufsteigender Reihenfolge der Summe beibehalten. Diese Eigenschaft wird beibehalten, indem der Nachfolger jeder neu gefundenen Teilsequenz überprüft und gelöscht wird, wenn ihre Summe nicht groß genug ist, und wiederholt wird, bis eine Teilsequenz mit einer größeren Summe erreicht ist oder das Ende der Liste erreicht ist.
quelle
Python, O (n log n)
Ich habe eine Indextransformation und eine raffinierte Datenstruktur (binär indizierter Baum) verwendet, um das Problem zu trivialisieren.
Der binär indizierte Baum kann zwei Operationen in log (n) ausführen: Erhöhen Sie einen Wert am Index i und erhalten Sie den Maximalwert in [0, i). Wir initialisieren jeden Wert im Baum mit 0. Wir indizieren den Baum anhand des Ranges der Elemente, nicht anhand ihres Index. Dies bedeutet, dass, wenn wir den Baum am Index i indizieren, alle Elemente [0, i) die Elemente sind, die kleiner sind als die mit Rang i. Dies bedeutet, dass wir das Maximum aus [0, i) erhalten, den aktuellen Wert hinzufügen und bei i aktualisieren. Das einzige Problem ist, dass dies Werte enthält, die kleiner als der aktuelle Wert sind, aber später in der Sequenz erscheinen. Da wir uns jedoch von links nach rechts durch die Sequenz bewegen und alle Werte im Baum auf 0 initialisieren, haben diese den Wert 0 und wirken sich daher nicht auf das Maximum aus.
quelle
Python 2 -
O(n^2)
- 114 Bytesquelle
C ++ -
O(n log n)
- 261 BytesSollte jetzt behoben sein:
quelle
auto S=set<pair<I,I>>();
ist länger als einfachset<pair<I,I>> S;
.#define I int
ist länger alsusing I=int;
. Es gibt keine Notwendigkeit zuweisenn
zu etwas, können Sie ersetzenauto n=*prev(S.lower_bound({w,-1}));I y=n.second
mitI y=prev(S.lower_bound({w,-1}))->second+w;
.S
ist sehr kompliziert. Sie können einfach auf das Einfügen verzichten und es verwendenstd::set<std::pair<int,int>>S{{-1,0}};
.using namespace std;using I=int;I h(vector<I>l){I W=0;set<pair<I,I>>S{{-1,0}};for(I w:l){I y=prev(S.lower_bound({w,-1}))->second+w;W=max(W,y);S.insert({w,y});}return W;}
std::max
, VerwendungW=y>W?y:W;
.Matlab, O ( n 2 n ), 90 Bytes
Beispiele:
quelle
Python, O (2 n ), 91 Bytes
Dies ist mehr zum Spaß als um wettbewerbsfähig zu sein. Eine arkane rekursive Lösung:
quelle
max(m,l[0])
angesichts dessennot(l[0]<m)
ist das dochl[0]
sicher?