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

Question

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

Например:

комплект = 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 

Answer 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) - после этого все сделано в линейном сканировании массива.

Answer 2

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

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