Самая длинная подпоследовательность, в которой разница между соседними элементами равна либо A, либо B.

Дан массив arr размера N и два целых числа A и B . Задача состоит в том, чтобы найти длину самой длинной подпоследовательности с разницей между соседними элементами как A или B .

Пример:

Input  : arr[]={ 5, 5, 5, 10, 8, 6, 12, 13 }, A=0, B=1
Output : 4
Explanation : Maximum length subsequence is {5,5,5,6}

Input  : arr[] = {4, 6, 7, 8, 9, 8, 12, 14, 17, 15}, A=2, B=1
Output : 6

Подход : при более внимательном рассмотрении проблемы она аналогична самой длинной последовательной последовательности. Единственная разница между ними в том, что теперь мы должны подсчитывать элементы с различиями A или B вместо 1 . Теперь, чтобы решить эту проблему, выполните следующие действия:

1. Создайте карту, которая будет хранить каждый элемент в качестве ключа и длину самой длинной подпоследовательности, заканчивающейся на arr[i] в качестве значения.
2. Теперь пройдитесь по массиву arr и для каждого элемента arr[i] :
   • Поиск arr[i]-A , arr[i]+A , arr[i]-B , arr[i]+B на карте.
   • Если они присутствуют, найдите максимум всех и +1 , чтобы получить максимальную длину подпоследовательности.
3. Найдите максимальное значение на карте и верните его в качестве ответа

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N)
Вспомогательное пространство: O(N)