查找所有可能子集的MAX和MIN差异的总和

Question

给定一组元素,如何在此列表的所有子集中找到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

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)之后,一切都在阵列的线性扫描中完成.