尋找所有可能子集的最大和最小差異的總和

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;