题目地址：

https://leetcode.com/problems/sum-of-subsequence-widths/description/

给定一个长nnn数组AAA，其任意子序列的振幅定义为该子序列的最大值与最小值之差。求AAA的所有子序列的振幅的总和。答案模109+710^9+7109+7后返回。

所有子序列的振幅等价于所有子集的振幅，与元素顺序无关，所以可以先将AAA排序，那么A[i]A[i]A[i]作为最大值的子集个数即为2i2^i2i，而其作为最小值的子集个数为2n−1−i2^{n-1-i}2n−1−i，所以答案就是∑i=0n−1A[i](2i−2n−1−i)\sum_{i=0}^{n-1} A[i](2^i-2^{n-1-i})i=0∑n−1​A[i](2i−2n−1−i)代码如下：

class Solution {public:int sumSubseqWidths(vector& a) {const int MOD = 1e9 + 7;sort(a.begin(), a.end());int n = a.size();long f[n];f[0] = 1;for (int i = 1; i < n; i++) f[i] = 2 * f[i - 1] % MOD;long res = 0;for (int i = 0; i < n; i++)res = (res + (f[i] - f[n - 1 - i]) * a[i]) % MOD;return (res + MOD) % MOD;}
};

时间复杂度O(nlog⁡n)O(n\log n)O(nlogn)，空间O(n)O(n)O(n)。