Минимальное произведение максимального и минимального элемента по всем возможным подмассивам

Дан массив arr[] , состоящий из N положительных целых чисел, задача состоит в том, чтобы найти минимальное произведение максимума и минимума среди всех возможных подмассивов.

Примеры:

Input: arr[] = {6, 4, 5, 6, 2, 4}
Output: 8
Explanation:
Consider the subarray {2, 4}, the product of minimum and maximum for this subarray is 2*4 = 8, which is minimum among all possible subarrays.

Input: arr[] = {3, 1, 5, 2, 3, 2}
Output: 3

Наивный подход: самый простой подход к решению данной проблемы — сгенерировать все возможные подмассивы массива и найти произведение максимального и минимального всех возможных подмассивов. После проверки всех подмассивов выведите минимум всех полученных произведений.

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

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

Следовательно, идея состоит в том, чтобы найти минимальное произведение всех пар смежных элементов, чтобы найти результирующее минимальное произведение.

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

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