Schwerste zunehmende Folge

9

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.

orlp
quelle
Wie wollen Sie mit unvergleichlichen Asymptotika umgehen? Es gibt möglicherweise zwei wichtige Variablen: die Länge der Sequenz und die Größe des größten Elements in der Sequenz.
Peter Taylor
@PeterTaylor Ich wähle die Länge der Sequenz als asymptotisch. Ihre Lösung darf keine Bindung an die Ganzzahlen annehmen und insbesondere keinen Speicher basierend auf der Größe der beteiligten Zahlen schleifen oder zuweisen. Ihnen wird vergeben, wenn Ihre Sprachwahl Ganzzahlen begrenzt hat, aber Sie dürfen diese Tatsache in Ihrer Lösung nicht nutzen. Befriedigt das Ihre Bedenken?
Orlp
Teilweise. Es ist theoretisch immer noch möglich (obwohl wahrscheinlich unwahrscheinlich), dass die Tatsache, dass der Vergleich zweier unbegrenzter Ganzzahlen eine Größe proportional zu ihrem Protokoll hat, relevant sein könnte. Möglicherweise möchten Sie zulassen, dass grundlegende Operationen (Addition, Vergleich, möglicherweise Multiplikation) für die Ganzzahlen als O (1) -Zeit angenommen werden.
Peter Taylor
@PeterTaylor Ist das transdichotome Berechnungsmodell spezifisch genug?
Orlp
Scheint vernünftig.
Peter Taylor

Antworten:

3

Javascript (ES6) O(n log n)253 Zeichen

function f(l){l=l.map((x,i)=>[x,i+1]).sort((a,b)=>a[0]-b[0]||1)
a=[0]
m=(x,y)=>x>a[y]?x:a[y]
for(t in l)a.push(0)
t|=0
for(j in l){for(i=(r=l[j])[1],x=0;i;i&=i-1)x=m(x,i)
x+=r[0]
for(i=r[1];i<t+2;i+=i&-i)a[i]=m(x,i)}for(i=t+1;i;i&=i-1)x=m(x,i)
return x}

Dies 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

stolzer haskeller
quelle
4

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_subseqFunktion, und unten befindet sich auch ein Testkabelbaum.

import bisect
import blist

def heaviest_subseq(in_list):
    best_subseq = blist.blist([(0, 0)])
    for new_elem in in_list:

        insert_loc = bisect.bisect_left(best_subseq, (new_elem, 0))

        best_pred_subseq_val = best_subseq[insert_loc - 1][1]

        new_subseq_val = new_elem + best_pred_subseq_val

        list_len = len(best_subseq)
        num_deleted = 0

        while (num_deleted + insert_loc < list_len
               and best_subseq[insert_loc][1] <= new_subseq_val):
            del best_subseq[insert_loc]
            num_deleted += 1

        best_subseq.insert(insert_loc, (new_elem, new_subseq_val))

    return max(val for key, val in best_subseq)

tests = [eval(line) for line in """[]
[3]
[3, 2, 1]
[3, 2, 5, 6]
[9, 3, 2, 1, 4]
[3, 4, 1, 4, 1]
[9, 1, 2, 3, 4]
[1, 2, 4, 3, 4]
[9, 1, 2, 3, 4, 5, 10]
[3, 2, 1, 2, 3]""".split('\n')]

for test in tests:
    print(test, heaviest_subseq(test))

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 Gesamtlaufzeit O(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.

isaacg
quelle
Interessant, eine ganz andere Lösung als meine .
Orlp
2

Python, O (n log n)

Ich habe eine Indextransformation und eine raffinierte Datenstruktur (binär indizierter Baum) verwendet, um das Problem zu trivialisieren.

def setmax(a, i, v):
    while i < len(a):
        a[i] = max(a[i], v)
        i |= i + 1

def getmax(a, i):
    r = 0
    while i > 0:
        r = max(r, a[i-1])
        i &= i - 1
    return r

def his(l):
    maxbit = [0] * len(l)
    rank = [0] * len(l)
    for i, j in enumerate(sorted(range(len(l)), key=lambda i: l[i])):
        rank[j] = i

    for i, x in enumerate(l):
        r = rank[i]
        s = getmax(maxbit, r)
        setmax(maxbit, r, x + s)

    return getmax(maxbit, len(l))

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.

orlp
quelle
1

Python 2 - O(n^2)- 114 Bytes

def h(l):
 w=0;e=[]
 for i in l:
    s=0
    for j,b in e:
     if i>j:s=max(s,b)
    e.append((i,s+i));w=max(w,s+i)
 return w
Tyilo
quelle
1

C ++ - O(n log n)- 261 Bytes

Sollte jetzt behoben sein:

#include <set>
#include <vector>
int h(std::vector<int>l){int W=0,y;std::set<std::pair<int,int>>S{{-1,0}};for(w:l){auto a=S.lower_bound({w,-1}),b=a;y=prev(a)->second+w;for(;b!=S.end()&&b->second<=y;b++){}a!=b?S.erase(a,b):a;W=y>W?y:W;S.insert({w,y});}return W;}
Tyilo
quelle
auto S=set<pair<I,I>>();ist länger als einfach set<pair<I,I>> S;. #define I intist länger als using I=int;. Es gibt keine Notwendigkeit zuweisen nzu etwas, können Sie ersetzen auto n=*prev(S.lower_bound({w,-1}));I y=n.secondmit I y=prev(S.lower_bound({w,-1}))->second+w;.
Orlp
Oh, und die Initialisierung von Sist sehr kompliziert. Sie können einfach auf das Einfügen verzichten und es verwenden std::set<std::pair<int,int>>S{{-1,0}};.
Orlp
@orlp danke! Es zeigt, dass ich kein c ++
benutze
Hier ist eine viel kürzere Version (benötigt noch die Menge und den Vektor enthalten):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;}
Orlp
Oh und Dump die std::max, Verwendung W=y>W?y:W;.
Orlp
0

Matlab, O ( n 2 n ), 90 Bytes

function m=f(x)
m=0;for k=dec2bin(1:2^numel(x)-1)'==49
m=max(m,all(diff(x(k))>0)*x*k);end

Beispiele:

>> f([])
ans =
     0
>> f([3])
ans =
     3
>> f([3, 2, 5, 6])
ans =
    14
Luis Mendo
quelle
0

Python, O (2 n ), 91 Bytes

Dies ist mehr zum Spaß als um wettbewerbsfähig zu sein. Eine arkane rekursive Lösung:

h=lambda l,m=0:l and(h(l[1:],m)if l[0]<=m else max(h(l[1:],m),l[0]+h(l[1:],l[0])))or 0
orlp
quelle
1
max(m,l[0])angesichts dessen not(l[0]<m)ist das doch l[0]sicher?
Peter Taylor
@ PeterTaylor Derp.
Orlp
Diese Antwort scheint kein ernstzunehmender Anwärter zu sein.
pppery