Произведение максимумов всех подмножеств массива
Дан массив arr[] , состоящий из N положительных целых чисел, задача состоит в том, чтобы найти произведение максимального числа всех возможных подмножеств данного массива. Поскольку произведение может быть очень большим, выведите его по модулю (109 + 7).
Примеры:
Input: arr[] = {1, 2, 3}
Output:
Explanation:
All possible subsets of the given array with their respective maximum elements are:
- {1}, the maximum element is 1.
- {2}, the maximum element is 2.
- {3}, the maximum element is 3.
- {1, 2}, the maximum element is 2.
- {1, 3}, the maximum element is 3.
- {2, 3}, the maximum element is 3.
- {1, 2, 3}, the maximum element is 3.
The product of all the above maximum element is 1*2*3*2*3*3*3 = 324.
Input: arr[] = {1, 1, 1, 1}
Output: 1
Наивный подход: самый простой подход к решению данной проблемы состоит в том, чтобы сгенерировать все возможные подмножества данного массива и найти произведение максимума всех сгенерированных подмножеств по модулю (10 9 + 7) в качестве результирующего произведения.
Временная сложность: O(N* 2N )
Вспомогательное пространство: O(1)
Эффективный подход. Описанный выше подход также можно оптимизировать на основе следующих наблюдений:
- Идея состоит в том, чтобы подсчитать, сколько раз каждый элемент массива встречается как максимальный элемент среди всех возможных сформированных подмножеств.
- Элемент массива arr[i] является максимальным тогда и только тогда, когда все элементы, кроме arr[i] , меньше или равны ему.
- Следовательно, количество подмножеств, образованных всеми элементами, меньшими или равными каждому элементу массива arr[i] , способствует подсчету подмножеств, имеющих arr[i] в качестве максимального элемента.
Выполните следующие шаги, чтобы решить проблему:
- Инициализируйте переменную, скажем, maximumProduct как 1 , которая хранит результирующее произведение максимальных элементов всех подмножеств.
- Отсортируйте заданный массив arr[] в порядке возрастания.
- Пройдите массив с конца, используя переменную i , и выполните следующие шаги:
- Найдите количество подмножеств, которые меньше текущего элемента arr[i] как (2 i – 1) и сохраните его в переменной, скажем, P .
- Поскольку элемент массива arr[i] вносит вклад P раз, поэтому умножьте значение arr[i] , P раз, на переменную maximumProduct .
- Найдите произведение элемента массива с maxProduct для включения всех подмножеств размера 1 .
- После выполнения вышеуказанных шагов выведите значение maxProduct как результирующий максимальный продукт.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O (N * log N)
Вспомогательное пространство: O(N)