Найдите сумму разности максимума и минимума по всем возможным подмножествам размера K
Дан массив arr[] из N целых чисел и целое число K , задача состоит в том, чтобы найти сумма разница между максимальным и минимальным элементами по всем возможным подмножествам размера K .
Примеры:
Input: arr[] = {1, 1, 3, 4}, K = 2
Output: 11
Explanation:
There are 6 subsets of the given array of size K(= 2). They are {1, 1}, {1, 3}, {1, 4}, {1, 3}, {1, 4} and {3, 4}.
The values of maximum – minimum for each of the subsets respectively are 0, 2, 3, 2, 3, 1 and their sum is 11.Input: arr[] = {1, 1, 1}, K = 1
Output: 0
Подход: Данная проблема может быть решена на основе следующих наблюдений:
- Сумма разности между максимумом и минимумом из всех наборов не зависит друг от друга, т. е. может быть вычислена как сумма максимума из всех наборов размера K – сумма минимума из всех наборов размера K .
- В отсортированном массиве arr[] arr[i] является максимальным из всех наборов, имеющих элементы из массива в диапазоне [0, i – 1] . Следовательно, количество наборов размера K, имеющих arr[i] в качестве максимального элемента массива, можно рассчитать как
. Точно так же количество наборов размера K, имеющих arr[i] в качестве минимального элемента, равно 
. - Значение
можно эффективно рассчитать, используя подход, обсуждаемый в этой статье.
Используя приведенные выше наблюдения, данную проблему можно решить, выполнив следующие шаги:
- Отсортируйте заданный массив arr[] в порядке неубывания.
- Чтобы вычислить сумму максимума всех наборов размера K , создайте переменную sumMax и для каждого индекса i в диапазоне [K – 1, N – 1] , выполните итерацию по массиву arr[] и добавьте
в суммуМакс . - Точно так же, чтобы вычислить сумму минимума всех наборов размера K , создайте переменную sumMin и для каждого i в диапазоне [0, NK] выполните итерацию по массиву arr[] и добавьте
в суммуМин . - Значение sumMax – sumMin является требуемым ответом.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O (N * log N)
Вспомогательное пространство: O(N)