Rilevare una sottosequenza che è una progressione aritmetica, in una sequenza ordinata

Question

Ho seguito un problema: ho una sequenza ordinata di interi $ n $ (supponiamo che stiano aumentando monotonicamente). Voglio verificare se esiste una successione di lunghezza $ ge n/4 $, in modo tale che gli elementi consecutivi della sottosequenza differiscano per lo stesso valore.

Ad esempio, nella sequenza [3,4,5,8,12] ci sono due di questi successioni: [3,4,5] (la differenza è 1) e [4,8,12] (la differenza è 4) . Pertanto, la lunghezza del più lungo di tale sottosequenza è 3 per questo esempio. Poiché $ 3 ge 5/4 $, la risposta è sì, c'è una sottosequenza di lunghezza $ ge n/4 $ con la proprietà desiderata.

Nella mia situazione nella vita reale, la sequenza è di lunghezza $ n circa 10^6 $ e gli elementi sono tutti numeri a 9 cifre. Esiste un algoritmo efficiente per risolvere questo problema?

---

Il mio approccio ingenuo era quello di creare un prodotto cartesiano con differenze assolute tra i numeri:

$$ Left ( Begin {Array} {ccccc} 0 & 1 & 2 & 5 & 9 1 & 0 & 1 & 4 & 8 2 & 1 & 0 & 3 & 7 5 & 4 & 3 & 0 & 4 9 & 8 & 7 & 4 & 0 end {array} a destra) $$

E poi concentrati sulla parte in alto a destra e calcola il numero di occorrenze di ciascuna differenza, quindi:

$$ || text {diff-by-1} || = 2 => text {3 numeri diff di 1} || text {diff-by-4} || = 2 => text {3 numeri diff di 4} $$

Questo è molto semplice e molto inefficace. Richiede molti confronti e non si ridimensiona (il suo tempo di esecuzione è $ theta (n^2) $. Nel mio scenario della vita reale la mia sequenza è lunga ~ 10^6, quindi è troppo lento.

Per darti un'immagine più ampia come forse c'è un approccio molto migliore (probabilistico) a questo problema: dopo che si trova la più grande sottosequenza, voglio calcolare un rapporto semplice:

$$ r: = frac { text {la più grande lunghezza della sotto-sequenza} { text {lunghezza della sequenza}} $$

E se $ R $ è maggiore di un valore fisso che voglio aumentare la sveglia (o fare tutto ciò che devo fare ;-)).

Grazie per qualsiasi aiuto, riferimenti, puntatori, ecc.

BTW: ecco le cose che stavo/sto guardando:

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

Aggiornare: ci pensavo un po 'di più e è iniziato dalla fine, quindi invece di calcolare tutte le differenze tra i numeri (angolo in alto a destra della matrice) posso derivare un piccolo valore $ k $ da "valore fisso" che ho menzionato alla fine di domanda originale. Ad esempio, se ho intenzione di aumentare l'allarme quando il 25% di tutti i numeri è in una sequenza, ho bisogno di concentrarmi su piccoli "triangoli" in matrice e il numero di calcoli richiesti è più piccolo (molto più piccolo). Quando aggiungo un po 'di campionamento, dovrebbe essere abbastanza semplice da implementare su vasta scala.

Aggiornamento 2 - Algoritmo @DW implementato, campione di seguito:

    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