Максимизируйте произведение минимального значения подмассива и суммы подмассива по всем подмассивам длины K

Учитывая массив arr[] из N целых чисел, задача состоит в том, чтобы найти максимально возможное значение ( min * sum ) среди всех возможных подмассивов, содержащих K элементов, где min обозначает наименьшее целое число подмассива, а sum обозначает сумму всех элементов подмассива.

Пример :

Input: arr[] = {1, 2, 3, 2}, K = 3
Output: 14
Explanation: For the subarray {2, 3, 2}, the score is given as min(2, 3, 2) * sum(2, 3, 2) = 2 * 7 = 14, which is the maximum possible.

Input: arr[] = {3, 1, 5, 6, 4, 2}, K = 2
Output: 55

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

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

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