Количество подпоследовательностей AP (арифметическая прогрессия) в массиве

Опубликовано: 20 Января, 2022

Дан массив из n натуральных чисел. Задача состоит в том, чтобы подсчитать количество подпоследовательностей арифметической прогрессии в массиве. Примечание. Пустая последовательность или последовательность из одного элемента - это арифметическая прогрессия. 1 <= arr [i] <= 1000000.
Примеры:

 Ввод: arr [] = {1, 2, 3}
Выход: 8
Подпоследовательность арифметической прогрессии из 
заданный массив: {}, {1}, {2}, {3}, {1, 2},
{2, 3}, {1, 3}, {1, 2, 3}.

Ввод: arr [] = {10, 20, 30, 45}
Выход: 12

Ввод: arr [] = {1, 2, 3, 4, 5}
Выход: 23

Рекомендуется: сначала решите эту проблему на «ПРАКТИКЕ», прежде чем переходить к решению.

Поскольку пустая последовательность и последовательность из одного элемента также являются арифметической прогрессией, поэтому мы инициализируем ответ n (количество элементов в массиве) + 1.
Теперь нам нужно найти подпоследовательность арифметической прогрессии длиной больше или равной 2. Пусть минимум и максимум массива равны minarr и maxarr соответственно. Обратите внимание: во всех подпоследовательностях арифметической прогрессии диапазон общих различий будет от (minarr - maxarr) до (maxarr - minarr). Теперь для каждой общей разницы, скажем, d, вычислите подпоследовательность длиной больше или равной 2, используя динамическое программирование.
Пусть dp [i] будет номером подпоследовательности, заканчивающейся на arr [i] и имеющей общую разность d. Так,

Количество подпоследовательностей длины больше или равной 2 с общей разностью d равно сумме dp [i] - 1, 0 <= i = 2 с разностью d. Для ускорения сохраните сумму dp [j] с arr [j] + d = arr [i] и j <i.
Ниже представлена реализация вышеизложенной идеи:

Выход :

 8

Автор статьи - Анудж Чаухан. Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью, используя write.geeksforgeeks.org, или отправить свою статью по электронной почте: deposit@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

РЕКОМЕНДУЕМЫЕ СТАТЬИ