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

Быстрее N^2, по-видимому, решения нет. Другое дело - с какой константой: тут можно в оптимизациях уйти очень далеко. Такая задача была на timus, можно оценить времена работы творений некоторых авторов, хотя чужие решения там вряд ли можно найти.

 

Кстати если множество чисел достаточно велико и известно заранее, то у меня есть одна конечно бредовая(тапком бить не дам), но всё-таки какая-никакая идея. Создать массив длинной [0..int] (или сколько там требуется) и при первом проходе по массиву делать inc элемента массива, который соответствует этому числу, а потом при проходе можно одновременно читать длинну прогрессии и как бы сортировать.

То есть дано скажем 3,4,7,0,0,1,1,1,1,1
тогда a[0]=2,a[1]=5,a[3]=1,a[4]=1,a[7]=1 как вам такой алгоритм? (если я понял, то там числа ограничены по величине, а про ограничение на память ничего не сказано)

 

То есть как бы вбивать это число столько раз сколько оно встречается в текте.. Сортировка! xD

 

MEPOX

 

MEPOX
Там вопрос не в том как сохранять промежуточные результаты поиска, а в том, что сравнить придётся "всё со всеми", потому и сравнений (N^2)/2 это без учёта вспомогательных построений вроде твоей таблицы, кстати как ты в ней собрался учитывать возможность вхождения одного числа в две прогресии? и вообще ты там предлагаешь идентифицировать прогрессию по одному числу - какому? - первому/последнему?.