leetcode891：子序列宽度之和

题目表述：

一个序列的 宽度 定义为该序列中最大元素和最小元素的差值。

给你一个整数数组 nums ，返回 nums 的所有非空 子序列 的 宽度之和 。由于答案可能非常大，请返回对 109 + 7 取余 后的结果。

子序列 定义为从一个数组里删除一些（或者不删除）元素，但不改变剩下元素的顺序得到的数组。例如，[3,6,2,7] 就是数组 [0,3,1,6,2,2,7] 的一个子序列。

示例 1：

输入：nums = [2,1,3]
输出：6
解释：子序列为 [1], [2], [3], [2,1], [2,3], [1,3], [2,1,3] 。
相应的宽度是 0, 0, 0, 1, 1, 2, 2 。
宽度之和是 6 。
示例 2：

输入：nums = [2]
输出：0
 

提示：

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5

大致思路：

因为求每个子序列的宽度（即子序列中最大值和最小值的差）。和数组顺序无关，将nums数组排序。

分清楚数组中的每个元素在所有子序列中当最大值和最小值的次数。例如【3，2，1】，排序完成后为【1，2，3】.子序列为[1], [2], [3], [2,1], [2,3], [1,3], [2,1,3] 。

1作为最大值的子序列只有【1】。

2作为最大值的有【2】，【1，2】。

3作为最大值有【3】，【1，3】，【2，3】，【1，2，3】.

可以看出来如果数组元素是按照从小到大的顺序。作为最大值的元素次数就是2^i次方。相反，最小值就是2^n(n-1-i)次方。这样如果当前元素最大值次数*当前元素nums【i】减去当前元素最小值出现次数，所有元素相加起来就是所有子序列宽度之和。

完整代码：

class Solution {
public:
    int sumSubseqWidths(vector<int>& nums) {
        const long long P=1000000000+7;
        sort(nums.begin(),nums.end());
        vector<long long>path(nums.size(),1);
        for(int i=1;isize();i++)
        {
            path[i]=path[i-1]*2%P;
        }
        long long count_s=0;
        for(int i=0;isize();i++)
        {
        count_s=(count_s+nums[i]*(path[i]-path[nums.size()-1-i]))%P;
        }
        return (int)count_s;
    }
};