Задачка. Поиск арифметической прогрессии максимальной длины.

Есть последовательность целых чисел. Нужно в ней выделить числа, которые образуют арифметическую прогрессию максимальной длины. Существует ли алгоритм, который это может сделать за O(n^2) или быстрее?

 

Ах да, забыл, числа расположены в случайном порядке.

 

Так нужно выбрать подпоследовательность чисел? или составить прогрессию независимо от их исходного порядка?

 

сортируешь и пробегаешься. O(n * log(n))

 

Можно и за o(n) управиться

 

Выбрать подпоследовательность.
Про O(n) ммм??? Расскажите вашу идею, пожалуйста.
Про O(n*logn) А пробежка то как раз O(n^2)

 

сама пробежка O(n). В сумме - O(n * (log(n) + 1))

 

а, если подпоследовательность, тогда вообще все просто -- O(n) и не нужно сортировки.

 

Мы правильно друг друга поняли?
Подпоследовательность, которая является самой длинной арифметической прогрессией.
Например, для
5 12 121 7 1 14 3 9 44 -10
Это будет 1 3 5 7 9

 

значит сортировка будет нужна, и всё как я написал.

 

А подробнее про пробежку можете рассказать?
ну есть у нас

-11 1 4 3 5 8 7 9 11 40 99

Как за линейное время определить самую длинную арифметическую прогрессию?

 

jaja

Это уже не подпоследовательность. Подпоследовательность - это выборка без перестановок.

 

Думаю можно сделать так:
Каждое следующее число вычитать из всех предидущих, разность брать по модулю, и запоминать в таблице найденных разностей (шагов прогрессии), если новой разности в таблице ещё нет, то добавить её туда. Каждому помещённому в таблицу шагу прогрессии сопоставлять счётчик длины и список образующих эту разность значений. Самую длинную последовательность потом отсортировать.
А обойтись линейной сложностью... боюсь не удастся - от однократного вычитания всех из всех + поиск в таблице уже найденных разностей никуда не денешься.

 

Вычитание следующего из всех предидущих это n*n/2 вычитаний + поиск в таблице и сортировка резльтата будут зависеть от конкретных данных, но думаю в О(n^2) это уложится.

 

jaja
А числа в исходной последовательности разные? (то бишь это перестановка?)

 

Нет. Могут и повторяться.
Числа влезают в int_64

 

jaja
нечёткий вероятностный подход - o(n) )

оценка снизу >= 2;
оценка сверху <= MAX(чётных, нечётных, (чётных + нечётных)/2);

 

>Это уже не подпоследовательность. Подпоследовательность - это выборка без перестановок.
Если то что вы говорите правда, то сортировка не нужна. Если нет, то мне кажется что нужна.
Во всяком случае лично я ничего другого не вижу.

 

Кстати это будет O(N) если я правильно понял, что такое подпоследовательность.

 

гамильтонианом его,гамильтонианом!