寻找所有可能子集的最大和最小差异的总和

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;