求所有可能子集的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

@mukul你可以计算2的所有幂，并将它们存储在一个同时取mod的数组中，就像

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

Answer 2

对列表排序。

排序后，i'th元素将在所有（且仅）不包含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）-之后，一切都在阵列的线性扫描中完成。