Максимизируйте сумму средних двух подмножеств, образованных путем деления на них заданного массива.

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

Примеры :

Input:  N = 2, arr[] = {1, 3}
Output:  4.00
Explanation: Since there are only two elements, make two subsets as {1} and {3}.
Their sizes are 1 so mean for both will be 1.00 and 3.00 which sums to 4.00

Input:  N = 5, arr[] = {1, 2, 3, 4, 5}
Output: 7.50
Explanation: Since there are 5 elements in the array, divide the array as {1, 2, 3, 4} and {5}. 
Their sizes are 4 and 1 respectively. The mean for the first subset will be (1+2+3+4)/4 = 2.50 
and the mean of the other subset will be 5. Hence the sum of means will be 2.50+5.00 = 7.50
For any other subset division the sum of means will not be more than 7.50. 
Examples: {1, 2, 3} and {4, 5} the means will be (1+2+3)/3 and (4+5)/2 
which is 2.00 and 4.50 respectively which sums to 6.50 which is less than 7.50

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

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

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