Разделите массив на две части так, чтобы максимальное произведение было минимальным.

Дан массив целых чисел, arr[] размера N (<=16), задача состоит в том, чтобы разделить массив на 2 части так, чтобы максимальное произведение этих 2 половинок было минимальным. Найдите минимизированное максимальное произведение половины. Если массив пуст, выведите -1.

Примеры:

Input: arr[] = {3, 5, 7}
Output: 15
Explanation: The possible partitions are – 
-> {5, 7} , {3}  – here the products are 35 and 3 and maximum product is 35
-> {3, 7} , {5}  – here the products are 21 and 5 and maximum product is 21
-> {5, 3} , {7}  – here the products are 15 and 7 and maximum product is 15
-> {5, 7, 3} , {}  – here the products are 105 and 0 and maximum product is 105

Out of the maximum product obtained i.e. from 105, 35, 21 and 15, the minimum value is 15 and therefore our required answer is 15. 

Input: arr[] = { 10 }
Output: 10
Explanation: Since the array contains single element, the array cannot be further divided. Hence the first half contains 10 and the other half contains no element. Therefore, the answer is 10.

Подход: поскольку значение N меньше 16 , проблема может быть решена с помощью маскирования битов, поскольку умножьте все числа, которые находятся в позиции с установленными битами, и поместите их в одну сторону, аналогичным образом умножьте все позиции с неустановленными битами и сохраните их в другой половине найти максимум из них и сохранить его в наборе и, наконец, вернуть первый элемент набора.

Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте набор st[] для хранения возможных ответов по порядку.
• Перебрать диапазон [0, 2 ^N ), используя переменную i , и выполнить следующие задачи:
  • Инициализируйте переменные product1 и product2 как 1 .
  • Перебрать диапазон [0, N), используя переменную j , и выполнить следующие задачи:
    • Если i & (1 << j) истинно, то умножьте значение arr[j] на переменную product1 , иначе — на переменную product2.
  • Вставьте максимум product1 или product2 в набор st[].
• После выполнения вышеуказанных шагов выведите первое значение набора в качестве ответа.

Ниже приведена реализация описанного выше подхода.

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