Das Folgende ist mein Code für größte monotone Subsequenz (entweder steigend oder fallend). Ich hatte keine Forschung vor der Programmierung dieses und war mir nicht bewusst, dass es eine allgemeine Frage der Informatik ist. Aus meinen nachfolgenden Untersuchungen geht hervor, dass der allgemein akzeptierte effizienteste Algorithmus O (N log N) ist. Dies sind typischerweise dynamische Programmierlösungen, die zu dieser Zeit ein bisschen über meinen Kopf sind.größte monoton steigende oder abnehmende Subsequenz
Ich bin kein Experte für Algorithmen, aber ist nicht der folgende Code O (N)? Ich durchlaufe jede Liste zweimal, einmal um eine zunehmende Sequenz zu finden, einmal um sie zu verkleinern.
Ich würde auch jeden Rat bei der Reinigung zu schätzen wissen. Ich weiß, dass die Funktionen sehr duplikativ sind, aber ich konnte keinen guten Weg finden, alles auf einmal ohne die Wiederholung der zweiten Funktion zu tun.
def largest_monotonic_subsequence(lst):
def increasing(lst):
beg,end,best = 0,0,[0,0]
for i in range(len(lst)-1):
if lst[i] <= lst[i+1]:
end = i+1
if end - beg > best[1] - best[0]:
best = beg, end
else:
beg = i+1
return (best[0],best[1]+1)
def decreasing(lst):
beg,end,best = 0,0,[0,0]
for i in range(len(lst)-1):
if lst[i] >= lst[i+1]:
end = i+1
if end - beg > best[1] - best[0]:
best = beg, end
else:
beg = i+1
return (best[0],best[1]+1)
incr = increasing(lst)
decr = decreasing(lst)
return lst[slice(*max([incr,decr], key = lambda x: x[1]-x[0]))]
Aus Wikipedia zu umkehren „* Dieser Teilfolge ist nicht notwendigerweise zusammenhängende * oder einzigartig " –
[In Mathematik] (https://en.wikipedia.org/wiki/Subsequenz), eine Untersequenz ist eine Sequenz, die von einer anderen Sequenz abgeleitet werden kann, indem einige Elemente gelöscht werden, ohne die Reihenfolge der verbleibenden Elemente zu ändern. [...] Die Subsequenz sollte nicht mit Substring verwechselt werden. –
Hoppla. Diese Frage war also Teil eines MIT OCW-Kurses, dem ich meine SO half - nachdem ich ihn gelöst hatte, googelte ich nach "monoton wachsendem Test" und fand RTFM offenbar nicht genau genug. Wenn zusammenhängend kein Kriterium ist, kann ich offensichtlich sehen, warum dies ein schwierigeres Problem wäre. Entschuldigung für die dumme Frage. – Solaxun