Detección de una subsecuencia que es una progresión aritmética, en una secuencia ordenada

Question

Tengo el siguiente problema: tengo una secuencia ordenada de $ N $ enteros (supongo que están aumentando monotónicamente). Quiero verificar si hay alguna subsecuencia de longitud $ ge n/4 $, de modo que los elementos consecutivos de la posterior difieran en el mismo valor.

Por ejemplo, en la secuencia [3,4,5,8,12] hay dos de estas posteriores: [3,4,5] (la diferencia es 1) y [4,8,12] (la diferencia es 4) . Por lo tanto, la longitud de la posterior posterior más larga es 3 para este ejemplo. Dado que $ 3 ge 5/4 $, la respuesta es sí, hay una posterior a la longitud $ ge n/4 $ con la propiedad deseada.

En mi situación de la vida real, la secuencia es de longitud $ n aproximadamente 10^6 $, y los elementos son todos números de 9 dígitos. ¿Existe un algoritmo eficiente para resolver este problema?

---

Mi enfoque ingenuo era crear productos cartesianos con diferencias absolutas entre los números:

$$ izquierda ( begin {array} {ccccc} 0 & 1 & 2 & 5 & 9 1 & 0 & 1 & 4 & 8 2 & 1 & 0 & 3 & 7 5 & 4 & 4 & 4 & 4 & 4 & 3 & 0 & 4 9 & 8 & 7 & 4 & 0 END {Array} Right) $$

Y luego concéntrese en la parte superior derecha y calcule el número de ocurrencias de cada diferencia, entonces:

$$ || text {diff-by-1} || = 2 => text {3 números diff por 1} || text {diff-by-4} || = 2 => text {3 números diff por 4} $$

Esto es muy simple y muy ineficaz. Requiere muchas comparaciones y no escala (en absoluto): su tiempo de ejecución es $ theta (n^2) $. En mi escenario de la vida real, mi secuencia es de ~ 10^6 de largo, por lo que esto es demasiado lento.

Para darle una imagen más amplia, ya que tal vez haya un enfoque mucho mejor (probabilístico) para este problema: después de que se descubra la subsecencia más grande, quiero calcular la relación simple:

$$ R: = frac { text {Longitud de sub-sesionencia más grande}} { text {Longitud de secuencia}} $$

Y si $ R $ es mayor, entonces algún valor fijo quiero aumentar la alarma (o hacer lo que tenga que hacer ;-)).

Gracias por cualquier ayuda, referencia, punteros, etc.

Por cierto: Aquí hay cosas que estaba/estoy mirando:

• http://link.springer.com/article/10.1007/s00453-009-9376-2
• http://en.wikipedia.org/wiki/longest_incresing_subsequence_problem
• http://en.wikipedia.org/wiki/longest_common_subsequence_problem
• http://en.wikipedia.org/wiki/kalman_filter

Actualizar: Estaba pensando un poco más al respecto y comenzó desde el final, por lo que en lugar de calcular todas las diferencias entre los números (esquina superior derecha de la matriz), puedo obtener un pequeño valor de $ k $ del "valor fijo" que mencioné al final de pregunta original. Por ejemplo, si voy a aumentar la alarma cuando el 25% de todos los números están en alguna secuencia, necesito centrarme en pequeños "triángulos" en la matriz y el número de cálculos requeridos es menor (mucho más pequeño). Cuando agrego un poco de muestreo, entonces debería ser lo suficientemente simple como para implementar a escala.

Actualización 2 - Algoritmo @DW implementado, muestra ejecutada a continuación:

    11:51:06 ~$ time nodejs progression.js 
    L: 694000000,694000002,694000006,694000007,694000009,694000010,
        694000013,694000015,694000018,694000019,694000021,694000022,694000023,
    694000026,694000028,694000030,694000034,694000036,694000038,694000040,
    694000043,694000045,694000046,694000048,694000051,694000053,694000055,
    694000057,694000060,694000061,694000063,694000067,694000069,694000072,
    694000074,694000076,694000077,694000079,694000080,694000082,694000083,
    694000084,694000086,694000090,694000091,694000093,694000095,694000099,
    694000102,694000103,694000105,694000108,694000109,694000113,694000116,
    694000118,694000122,694000125,694000128,694000131,694000134,694000137,
    694000141,694000143,694000145,694000148,694000152,694000153,694000154,
    694000157,694000160,694000162,694000163,694000166,694000170,694000173,
    694000174,694000177,694000179,694000180,694000181,694000184,694000185,
    694000187,694000189,694000193,694000194,694000198,694000200,694000203,
    694000207,694000211,694000215,694000219,694000222,694000226,694000228,
    694000232,694000235,694000236
    N: 100
    P: 0.1
    L: 10 (min)
    D: 26 (max)
    [ 9, 18, 27, 36, 45, 54, 63, 72, 81, 90 ]
    Found progression of 10 elements, difference: 16 starts: 694000045, ends: 694000189.

    real    0m0.065s
    user    0m0.052s
    sys 0m0.004s