Geben Sie bei einer nicht leeren endlichen Folge von ganzen Zahlen eine arithmetische Teilfolge maximaler Länge zurück.
Wenn es mehrere gleiche maximale Länge gibt, kann jeder von ihnen zurückgegeben werden.
Definitionen:
Eine arithmetische Folge ist eine Folge a(1),a(2),a(3),a(4),...
, bei der es eine Konstante gibt c
, die a(m+1)-a(m) = c
für alle gilt m
. Mit anderen Worten: Der Unterschied zwischen zwei nachfolgenden Begriffen ist konstant.
Bei einer Sequenz b(1),b(2),b(3),b(4),...
einer Teilsequenz ist eine Sequenz , b(s(1)),b(s(2)),b(s(3)),b(s(4)),...
wo 1 <= s(1)
und s(m) < s(m+1)
für alle m
. Mit anderen Worten: Nehmen Sie die ursprüngliche Sequenz und entfernen Sie so viele Einträge, wie Sie möchten.
Beispiele
Input Output
[4,1,2,3,6,5] [1,3,5] or [1,2,3]
[5,4,2,-1,-2,-4,-4] [5,2,-1,-4]
[1,2,1,3,1,4,1,5,1] [1,1,1,1,1] or [1,2,3,4,5]
[1] [1]
Einige längere Testfälle:
Length: 25
Input: [-9,0,5,15,-1,4,17,-3,20,13,15,9,0,-6,11,17,17,9,26,11,5,11,3,16,25]
Output: [15,13,11,9] or [17,13,9,5]
Length: 50
Input: [35,7,37,6,6,33,17,33,38,30,38,12,37,49,44,5,19,19,35,30,40,19,11,5,39,11,20,28,12,33,25,8,40,6,15,12,27,5,21,6,6,40,15,31,49,22,35,38,22,33]
Output: [6,6,6,6,6] or [39,33,27,21,15]
Length: 100
Input: [6,69,5,8,53,10,82,82,73,15,66,52,98,65,81,46,44,83,9,14,18,40,84,81,7,40,53,42,66,63,30,44,2,99,17,11,38,20,49,34,96,93,6,74,27,43,55,95,42,99,31,71,67,54,70,67,18,13,100,18,4,57,89,67,20,37,47,99,16,86,65,38,20,43,49,13,59,23,39,59,26,30,62,27,83,99,74,35,59,11,91,88,82,27,60,3,43,32,17,18]
Output: [6,18,30,42,54] or [8,14,20,26,32] or [46,42,38,34,30] or [83,63,43,23,3] or [14,17,20,23,26] or [7,17,27,37,47] or [71,54,37,20,3]
Hintergrund
Ich kam auf diese Idee, als ich mich an das Green-Tao-Theorem von 2004 erinnerte, das besagt, dass die Folge von Primzahlen endliche arithmetische Folgen beliebiger Länge enthält.
diff
ergibt ein leeres Array, das nicht negiert werden kann.Python 2,
1241159897 BytesSehr langsam und speicherintensiv. Testen Sie es auf Ideone .
Alternative Version, 98 Bytes
Damit sind alle Testfälle sofort abgeschlossen. Testen Sie es auf Ideone .
quelle
Pyth Checkout 8593c76, 24. März , 10 Bytes
Dies ist genau das Gleiche wie die Antwort von Doorknob, außer dass es im März eine 2-Byte-Funktion (
q ... )
) gab, die prüfte, ob alle Elemente einer Liste gleich waren, was das gleiche ist wie!P{
das Beste, was Sie tun können zur Zeit.quelle
JavaScript (ES6), 157 Byte
Fast 20 mal länger als die Antwort von Jelly ... Ungolfed:
quelle