algorithm - 求所有可能子集的 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) - 之后，一切都在数组的线性扫描中完成。