Количество подпоследовательностей AP (арифметическая прогрессия) в массиве
Дан массив из 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.