LC891. 子序列宽度之和

Posted on | Post modified:

LC891. 子序列宽度之和

题面

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

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

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

题解

  • 由于是子序列，因此和顺序无关，排序

  • 假设$nums[i]$是最大值，那么最小值只能是$nums[j] (j < i)$

  • 枚举最大值，则最大值产生的贡献为：

  • 拆分可得：

    使用两个前缀和维护即可

  • 时间复杂度$O(nlog(n))$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
const int mod = 1e9 + 7;

class Solution {
public:
    long long qpow(long long a, long long b){
        long long ans = 1;
        while(b){
            if(b & 1) ans = ans * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return ans % mod;
    }
    int sumSubseqWidths(vector<int>& nums) {
        int n =  (int)nums.size();
        sort(nums.begin(), nums.end());
        vector<long long> pre1(n), pre2(n);
        pre1[0] = qpow(qpow(2, 1), mod - 2);
        pre2[0] = nums[0] * pre1[0];

        for(int j = 1; j < n; j++){
            pre1[j] = pre1[j - 1] + qpow(qpow(2, j + 1), mod - 2);
            pre1[j] %= mod;
            pre2[j] = pre2[j - 1] + nums[j] * qpow(qpow(2, j + 1), mod - 2) % mod;
            pre2[j] %= mod;
        }
        long long ans = 0;
        for(int i = 1; i < n; i++){
            long long t1 = qpow(2, i);
            long long t2 = nums[i] * pre1[i - 1];
            t2 %= mod;
            long long t3 = pre2[i - 1];
            t3 %= mod;
            ans += (t1 * (t2 - t3 + mod) % mod) % mod;
            ans %= mod;
        }
        return ans;
    }
};