Нахождение суммы различий MAX и MIN всех возможных подмножеств

Учитывая набор элементов, как я могу найти разницу между MAX и MIN во всех подмножествах этого списка.

Например:

set = 1 2 3

Subset = {1}, max(s)-min(s) = 0.  
Subset = {2}, max(s)-min(s) = 0.
Subset = {3}, max(s)-min(s) = 0.
Subset = {1,2}, max(s)-min(s) = 1.
Subset = {2,3}, max(s)-min(s) = 1.
Subset = {1,3}, max(s)-min(s) = 2.
Subset = {1,2,3}, max(s)-min(s) = 2.

So the output will be 1+1+2+2 = 6

Ответы

Ответ 1

Сортировка списка.

После сортировки i-й элемент будет минимальным во всех (и только) подмножествах, которые не включают в себя первые элементы i-1, и не включает этот элемент. Есть 2^(n-i) тех (когда i на 1).

Аналогично, i будет наивысшим элементом в каждом подмножестве, который не содержит числа после i и включает i, и есть 2^(i-1) такие подмножества (опять же, 1 на основе).

Итак, после сортировки, просто повторите, и для каждого i добавьте:

arr[i] * (2^(i-1) - 2^(n-i))

Эффективно добавляя сумму на arr[i] * #times_i_is_max и уменьшая ее на arr[i] * #times_i_is_min

В вашем примере:

sorted=1,2,3
1* (2^0 - 2^2) + 2*(2^1 - 2^1) + 3*(2^2 - 2^0) =
1*(-3) + 2*0 + 3*(3) = -3 + 0 + 9 = 6

Узким местом этого алгоритма является сортировка, которая O(nlogn) - после этого все выполняется при линейном сканировании массива.

Ответ 2

@mukul вы можете рассчитать все степени 2 и сохранить их в массиве, принимающем мода одновременно как

a[0]=1; for(i=1;i<any_no;i++)a[i]=(a[i-1]*2)%MOD;