Tengo un millón de enteros ordenados y me gustaría encontrar la subsecuencia más larga en la que la diferencia entre pares consecutivos sea igual. Por ejemplo

1, 4, 5, 7, 8, 12

tiene una subsecuencia

   4,       8, 12

Mi ingenuo método es codicioso y solo comprueba hasta dónde puede extender una subsecuencia desde cada punto. Esto llevaO(n²) El tiempo por punto parece.

¿Hay una manera más rápida de resolver este problema?

Actualizar. Voy a probar el código dado en las respuestas tan pronto como sea posible (gracias). Sin embargo, ya está claro que el uso de la memoria n ^ 2 no funcionará. Hasta ahora no hay ningún código que termine con la entrada como[random.randint(0,100000) for r in xrange(200000)] .

Tiempos He probado con los siguientes datos de entrada en mi sistema de 32 bits.

a= [random.randint(0,10000) for r in xrange(20000)] 
a.sort()

El método de programación dinámica de ZelluX usa 1.6G de RAM y toma 2 minutos y 14 segundos. Con pypy solo toma 9 segundos! Sin embargo, se bloquea con un error de memoria en entradas grandes.El método de tiempo O (nd) de Armin tomó 9 segundos con pypy pero solo 20MB de RAM. Por supuesto, esto sería mucho peor si el rango fuera mucho mayor. El bajo uso de memoria significaba que también podía probarlo con a = [random.randint (0,100000) para r en xrange (200000)] pero no terminó en los pocos minutos que le di con pypy.

Para poder probar el método de Kluev's I reran con

a= [random.randint(0,40000) for r in xrange(28000)] 
a = list(set(a))
a.sort()

para hacer una lista de longitud aproximadamente20000. Todos los tiempos con pypy.

ZelluX, 9 segundosKluev, 20 segundosArmin, 52 segundos

Parece que si el método ZelluX pudiera hacerse espacio lineal sería el claro ganador.