Dada una secuencia finita no vacía de enteros, devuelve una subsecuencia aritmética de longitud máxima.
Si hay múltiples de la misma longitud máxima, cualquiera de ellos puede ser devuelto.
Definiciones:
Una secuencia aritmética es una secuencia a(1),a(2),a(3),a(4),...
tal que hay una constante c
tal que a(m+1)-a(m) = c
para todos m
. En otras palabras: la diferencia entre dos términos posteriores es constante.
Dada una secuencia, b(1),b(2),b(3),b(4),...
una subsecuencia es una secuencia b(s(1)),b(s(2)),b(s(3)),b(s(4)),...
donde 1 <= s(1)
y s(m) < s(m+1)
para todos m
. En otras palabras: tome la secuencia original y elimine tantas entradas como desee.
Ejemplos
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]
Algunos casos de prueba más largos:
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]
Antecedentes
Se me ocurrió esta idea cuando recordé el Teorema del Tao Verde de 2004, que establece que la secuencia de números primos contiene secuencias aritméticas finitas de longitud arbitraria.
diff
da una matriz vacía que no se puede negar.Python 2,
1241159897 bytesMuy lento e intensivo en memoria. Pruébelo en Ideone .
Versión alternativa, 98 bytes.
Esto completa todos los casos de prueba al instante. Pruébelo en Ideone .
fuente
Pyth checkout 8593c76, 24 de marzo , 10 bytes
Esto es exactamente lo mismo que la respuesta de Doorknob, excepto que en marzo, había una función de 2 bytes (
q ... )
) que verificaba si todos los elementos de una lista eran iguales, lo!P{
que es lo mejor que puedes hacer actualmente.fuente
JavaScript (ES6), 157 bytes
Casi 20 veces más que la respuesta de Jelly ... Ungolfed:
fuente