Максимальная сумма подмножества, имеющая разность между своим максимумом и минимумом в диапазоне [L, R]

Учитывая массив arr[] из N положительных целых чисел и диапазон [L, R] , задача состоит в том, чтобы найти максимальную сумму подмножества, такую, что разница между максимальным и минимальным элементами подмножества лежит в заданном диапазоне.

Примеры:

Input: arr[] = {6, 5, 0, 9, 1}, L = 0, R = 3
Output: 15
Explanation: The subset {6, 9} of the given array has the difference between maximum and minimum elements as 3 which lies in the given range [0, 3] and the sum of the elements as 15 which is the maximum possible.

Input: arr[] = {5, 10, 15, 20, 25}, L = 1, R = 2
Output: 0
Explanation: There exist no valid subsets.

Подход: Данная проблема может быть решена с помощью бинарного поиска после сортировки данного массива. Ниже приведены шаги, которые необходимо выполнить:

• Отсортируйте заданный массив в порядке неубывания.
• Создайте массив суммы префикса sum [] , используя алгоритм, обсуждаемый здесь.
• Пройдите массив, используя переменную i для всех значений i в диапазоне [0, N) .
• Для каждого i найдите индекс j наибольшего целого числа, такого что arr[j] <= arr[i] + R . Это можно сделать с помощью функции upper_bound.
• Сохраните переменную ans , в которой хранится максимальная сумма подмножества. Первоначально анс = 0 .
• Если подмассив arr[i, j] образует допустимое подмножество, обновите значение ans до максимального числа ans и суммы подмассива arr[i, j] .
• Значение, хранящееся в ans , является требуемым ответом.

Ниже приведена реализация вышеуказанного подхода:

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