Ьудем рассматривать все возможные разности (в виде i-начало, j-конец, i<j) в порядке возрастания. Но запоминать и сортировать их все нет нужды, чтобы получить их, воспользуемся идеей сортировки слиянием: N последовательностей
a(2)-a(1)...a(N)-a(1), a(3)-a(2)...a(N)-a(2) итд, их можно "слить" за O(N^2). Опять-таки, сливать все сразу не надо, надо выделить подряд идущую группу равных элементов (их не более N) и сохранить в промежуточный массив, далее работать с ними, потом брать следующую группу и так пока все сливаемые последовательности не закончатся. Первую группу, где величина разности=0, ессн-но не обрабатываем
Остается из группы k<=N разностей выделить макс.членов арифм.прогрессии, т.е. чтобы конец одной разности = началу другой. Используем массив размера N, где для каждого эл-та исходного массива храним счетчик = длине оканчивающегося в нем куска прогрессии. Первому эл-ту присваиваем счетчик=0. Одним проходом по группе разностей расставляем счетчики
(учитывая что разности изначально сортированы по i-начало в ходе слияния), счетчик[разность.конец]=счетчик[разность.начало]+1, в том же проходе запоминаем наибольший счетчик и последний эл-т, из которых за O(N) легко восстановить всю последовательность. Итого на группу O(k) действий, а в сумме O(N^2)