查找所有可能子集的最大值和最小值之差的总和

Question

给定一组元素，如何找到该列表的所有子集中最大值和最小值之间的差异。

例如：

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

- Aniruddha Paul

Answer 1

将列表排序。

排序后，第i个元素将是所有（且仅有的）不包括前i-1个元素并且包括该元素的子集中的最小值。当i从1开始算时，这样的子集有 2^(n-i) 个。

同样地，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) - 排序之后，数组的线性扫描就可以完成所有操作。

- amit

---

我明白你这样计算的逻辑，这是因为加法的交换律。老兄，你真聪明。 - Aniruddha Paul

如果问题涉及到%M，那么负数应该如何处理？ - Aniruddha Paul

负数总是用“％M”处理的方式。 - Teepeemm

如果我们使用 map 而不是 array，我认为它会更快，因为 map 会按排序顺序存储它们。我想知道这样做是否正确？只是一个疑问。 - pola sai ram

@polasairam 无论如何，您都需要对其进行排序，将元素填充到映射中也将是O(nlogn)。但是，映射上的常数会更糟，因为数组要简单得多。 - amit

Answer 2

@mukul 你可以计算所有的2的幂并同时取模存储在一个数组中。

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

- HIBUDDY