UPS ! Codzień jakaś wtopa .
No to pozostaje zastosować taki myk - tworzysz tablice n*2001 ( - 1000..1000 ). W tablicy zaznaczasz różnice między bierzącym elementem danych wejściowych a wszystkimi kolejnymi do końca .
9
1 0 7 9 12 13 14 15 19
Analizę danych zaczynasz od ostatniego elementu danych wejściowych
__| 0 1 2 3 4 5 6 7 8 ( index )
19| 0 0 0 0 0 0 0 0 0 ...
Będzie ona wypełniona samymi zerami . Dla przed ostatniego elementu
__| 0 1 2 3 4 5 6 7 8 ( index ) Iteracja 1
15| 0 0 0 0 1 0 0 0...
19| 0 0 0 0 0 0 0 0...
__| 0 1 2 3 4 5 6 7 8 ( index ) Iteracja 2
14| 0 1 0 0 0 1 0 0...
15| 0 0 0 0 1 0 0 0...
19| 0 0 0 0 0 0 0 0...
__| 0 1 2 3 4 5 6 7 8 ( index ) Iteracja 3`
13| 0 1 1 0 0 0 1 0
14| 0 1 0 0 0 1 0 0...
15| 0 0 0 0 1 0 0 0...
19| 0 0 0 0 0 0 0 0...
__| 0 1 2 3 4 5 6 7 8 ( index ) Iteracja 4
12| 0 1 1 1 0 0 0 1...
13| 0 1 1 0 0 0 1 0...
14| 0 1 0 0 0 1 0 0...
15| 0 0 0 0 1 0 0 0...
19| 0 0 0 0 0 0 0 0...
__| 0 1 2 3 4 5 6 7 8 ( index ) Iteracja 5
09| 0 0 0 1 1 1 1 0 0 0 1...
12| 0 1 1 1 0 0 0 1...
13| 0 1 1 0 0 0 1 0...
14| 0 1 0 0 0 1 0 0...
15| 0 0 0 0 1 0 0 0...
19| 0 0 0 0 0 0 0 0...
Jak nietrudno zauważyć - wszystkie dane w bieżącym wierszu w stosunku do wiersza poniżej , są przesunięte o różnice między wartościami kolejnych danych wejściowych ( wystarczy przekopiować odpowiednio przesuwając ) .
Złożoność dla brute force -- pewnie gdzieś w okolicy n*n/2*sqrt(n*2) .
Załóżmy że pierwsza liczba to 100 a druga to 600 to kolejny element takiego ciągu już wychodzi po za zakres 1000 i podciąg dla różnicy 500 będzie miał co najwyżej 2 elementy . Jeżeli znalazłeś już podciąg o długości 50 elementów to w dalszych poszukiwaniach nie ma sensu rozpatrywać większej różnicy miedzy elementami niż 20 .