LeetCode 891. 子序列宽度之和

枚举元素计算贡献

子序列，在这个题中，只关心子序列的最大值和最小值，而与子序列中数的顺序，因此可以对对数组排序后对结果不产生影响。

排完序之后可以看到对于一个数nums[i]来说，如果所在的子序列中它是最大的，那么它对结果的贡献就为正的+nums[i]。如果它在子序列中它为最小的，那么它对结果的贡献为负的即-nums[i]。
接下来问题就变成了寻找nums[i]在多少个子序列中为最大值，在多少个子序列中为最小值。
排完序之后（升序），我们可以发现，当nums[i]与只其前面的数和自身组成子序列时，nums[i]在所组成的子序列中为最大值，通过数学公式我们可以知道此时以nums[i]为最大值的子序列个数为$2^i$。同理当nums[i]只与自身和其后边数组成子序列时，所组成的子序列nums[i]为最小值，有$2^{n-1-1}$个

因此nums[i]对结果的贡献为$(2^i-2^{n-1-i})\ast nums[i]$，将所有元素的贡献求和，即可得到结果。

这个题还有一个需要注意的地方就是在计算2的指数时可能会溢出，因此也需要对2的指数进行模运算。这里可以用一个数组保存2指数运算的结果

class Solution {
public:
    int sumSubseqWidths(vector<int>& nums) {
        long long MOD = 1e9 + 7;
        int n = nums.size();
        int pow2[n];
        pow2[0] = 1;
        for(int i = 1; i < n; i++)
            pow2[i] = (pow2[i - 1] * 2) % MOD;
        int res = 0;
        sort(nums.begin(), nums.end());
        for(int i = 0; i < n; i++)
        {
            res = (res + long(pow2[i] - pow2[n - 1 - i]) * nums[i]) % MOD;
        }
        return (res + MOD) % MOD;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18