Произведение максимумов всех подмножеств массива

Опубликовано: 22 Сентября, 2022

Дан массив 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. {1}, the maximum element is 1.
  2. {2}, the maximum element is 2.
  3. {3}, the maximum element is 3.
  4. {1, 2}, the maximum element is 2.
  5. {1, 3}, the maximum element is 3.
  6. {2, 3}, the maximum element is 3.
  7. {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)

РЕКОМЕНДУЕМЫЕ СТАТЬИ