题目描述

给定一个整数数组 A ，考虑 A 的所有非空子序列。

对于任意序列 S ，设 S 的宽度是 S 的最大元素和最小元素的差。

返回 A 的所有子序列的宽度之和。

由于答案可能非常大，请返回答案模 10^9+7。

样例

输入：[2,1,3]
输出：6
解释：
子序列为 [1]，[2]，[3]，[2,1]，[2,3]，[1,3]，[2,1,3]。
相应的宽度是 0，0，0，1，1，2，2。
这些宽度之和是 6。

算法

(数学，递推) $O(n \log n)$

1. 将数组 A 从小到大排序。
2. 假如我们固定了当前子序列的最小值 $A[i]$，假设数组下标从 0 开始，则以 $A[i]$ 为最小值贡献的答案为，$(A[n - 1] - A[i])2^{n-i-2} + (A[n - 2] - A[i])2^{n-i-3} + \cdots + (A[i + 1] - A[i])2^{0}$。将括号打开，一部分为 $-A[i] \cdot (2^{n - i - 1} - 1)$，另一部分是 $S(i)=\sum_{k=i+1}^{n-1}{A[k] \cdot 2^{k-i-1}}$。
3. 第二部分不能每次枚举计算，但可以找到递推公式，即$S(i) = 2S(i+1) + A[i + 1]$，其中 $S(n-1)=0$。
4. 然后我们可以从 $i=n-2$ 开始到 $i=0$ 枚举统计答案即可。

时间复杂度

• 排序后线性扫描数组，故时间复杂度为 $O(n \log n)$。

C++ 代码

class Solution {
public:
    #define LL long long
    int sumSubseqWidths(vector<int>& A) {
        const int mod = 1000000007;
        int n = A.size();
        sort(A.begin(), A.end());

        vector<LL> p2(n);
        LL sum, ans = 0;

        p2[0] = 1;

        for (int i = 1; i < n; i++)
            p2[i] = p2[i - 1] * 2 % mod;

        sum = 0;

        for (int i = n - 2; i >= 0; i--) {
            sum = (sum * 2 + A[i + 1]) % mod;
            ans = (ans + sum - A[i] * (p2[n - i - 1] - 1)) % mod;
        }

        return (ans % mod + mod) % mod;
    }
};