Максимизировать сумму массива, кроме элементов из [i, i+X] для всех i таких, что arr[i] > K

Учитывая массив arr[] размера N и два целых числа X и K , задача состоит в том, чтобы найти максимальную оценку, которую можно получить, переставляя элементы массива, где оценка рассчитывается как сумма элементов массива, кроме следующие X элементов из индекса i таких arr[i] > K для всех возможных значений i в диапазоне [0, N) .

Пример:

Input: arr[] = {9, 13, 16, 21, 6}, X = 2, K = 15
Output: 50
Explanation: The given array can be rearranged as arr[] = {16, 6, 9, 13, 21}. The indices such that arr[i] > K are {0, 4}. Therefore, the next two elements from index 0 and index 4 will be skipped. Therefore, the sum of remaining elements becomes 16 + 13 + 21 = 50, which is the maximum possible.

Input: arr[] = {31, 20, 19, 23, 34, 21, 37}, X = 3, K= 22
Output: 112

Подход: Данную задачу можно решить с помощью жадного подхода. Создайте два массива: big[] , содержащий целые числа больше K , и small[] , содержащий целые числа меньше K. Можно заметить, что если число элементов, превышающих K , которые должны быть включены в сумму, равно i , то в массиве должно существовать не менее (i − 1)(X + 1) + 1 элементов. Следовательно, для каждого возможного i исключите ( (i − 1)(X + 1) + 1 ) – i наименьшие элементы массива small[] из общей суммы . Требуемым результатом является максимальное значение из всех возможных сумм для каждого i .

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

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