Как найти длину наибольшего непрерывного сегмента, который формирует арифметическую прогрессию в диапазоне [LR] данного массива длины N?

Question

Рассмотрим массив 1 2 3 5 5

1. для запроса [L R D]=[1 5 1], вывод 3
2. для запроса [1 1 1], вывод 1

Также есть Q запросов на этот вопрос, где 0<Q<10^6, так что Brute Forces не работает!

Примечание: индексация начинается с 1

Примечание2: D представляетобщая разница AP

Answer 1

Ваш вопрос может быть упрощен, чтобы найти длину самой длинной арифметической прогрессии с заданной общей разницей, с массивом = [L, R] и размером n = R - L + 1

Затем вы можете найти решение от Geeksforgeeks

Наивный подход : Для каждого элемента вычислите длину самого длинного AP, который он может сформировать, и выведите максимальное из них. Он включает в себя O (n ^ 2) временную сложность.

Эффективным подходом является использование Хеширование .

Создание карты, в которой ключ является начальным элементом AP. и его значение - количество элементов в этом AP. Идея состоит в том, чтобы обновить значение в ключе 'a' (который находится в индексе i и чей начальный элемент еще не находится на карте) на 1 всякий раз, когда элемент в индексе j (> i) может быть в AP 'a'(как начальный элемент). Затем мы печатаем максимальное значение среди всех значений на карте.