题目描述

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

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

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

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

其中，

1 <= A.length <= 20000

1 <= A[i] <= 20000

【注意】 数组的子序列相当于是数组的非空子集，个数一共有$2^n-1$个。

样例

输入：[2,1,3]
输出：6
解释：
子序列为 [1]，[2]，[3]，[2,1]，[2,3]，[1,3]，[2,1,3] 。
相应的宽度是 0，0，0，1，1，2，2 , 所以答案是6

算法1

(数学) $O(nlogn)$

【注意】以下思路来源于yxc老师的课堂视频笔记。如有错误，欢迎指正。

1. 由于只求每个子集的最大最小值，首先对数组进行排序。

   数组表示为$a[0],a[1],…,a[n-1]$.

2. 思路1：用(i,j) pair来给划分子集。

   每一个(i,j)对表示一组min=a[i], max=a[j]的子集，相当于在数组中固定a[i]和a[j]两端，中间的点任意选。

   这组子集一共有$2^{j-i-1}$个子集，每个子集的宽度是($a[j]-a[i]$)，那么这组子集的总宽度为$(a[j]-a[i])\*(2^{j-i-1})$.

3. 思路2(优化版)：用j来划分子集。

   每一组子集都是以a[j]结尾，相当于对思路1做i的压缩。

   由思路1的分析可得，

   $ result = (a[j]-a[0])\*(2^{j-0-1}) + (a[j]-a[1])\*(2^{j-1-1}) + … + (a[j]-a[j-1])\*(2^{j-j+1-1}) $

   可表示为 $result = X - Y$, 其中

   $X = a[j] \* (2^{j-1}+2^{j-2}+…+2^0) = a[j] \* (2^j -1)$,

   $Y = a[0]\*2^{j-1} + a[1]\*2^{j-2} + … + a[j-1]\*2^0$.

4. 简化计算 $result = X - Y$

   $X$的计算只需要在一次循环中遍历$a[j]$和维护$p=2^j$即可得。

   观察可得，$Y[j+1]=Y[j]+a[j]$。实例代码中用sum表示Y[j]。

复杂度分析 $O(nlogn)$

排序$O(nlogn)$, 求$X$和$Y$都在一个循环中完成，$O(n)$。

C++ 代码

// p代表2的多少次方，每一步循环中更新一次
// sum代表Y


class Solution {
public:

    int mod = 1000000007;

    int sumSubseqWidths(vector<int>& A) {
        sort(A.begin(), A.end());
        long long res = 0, p = 1, sum = 0;
        for (auto x : A)
        {
            res = (res + x * (p - 1) - sum) % mod;
            sum = (sum * 2 + x) % mod;
            p = p * 2 % mod;
        }
        return (res + mod) % mod;
    }
};

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/14784/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。