LeetCode 891. 子序列宽度之和（数学）

Michael阿明

发布于 2021-09-06 02:03:18

37000

代码可运行

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

运行总次数：0

代码可运行

文章目录

- 1. 题目
- 2. 解题

1. 题目

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

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

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

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

示例：
输入：[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 <= A.length <= 20000
1 <= A[i] <= 20000

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/sum-of-subsequence-widths 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

类似题目：

LeetCode 907. 子数组的最小值之和（单调栈）

天池在线编程所有子数组之和（排列组合）

class Solution {
public:
    int sumSubseqWidths(vector<int> &A) {
        long long ans = 0, mod = 1e9+7;
        long long n = A.size();
        sort(A.begin(), A.end());
        // 每个数作为最小值的时候，右侧有多少种方案 2^(n-i-1);
        // 每个数作为最大值的时候，左侧有多少种方案 2^(i);
        vector<long long> p2(n);
        p2[0] = 1;
        for(int i = 1; i < n; i++)
            p2[i] = (p2[i-1]<<1)%mod;
        for(int i = 0; i < n; ++i)
        {
            ans = (ans + (p2[i]-p2[n-i-1])*A[i])%mod;
        }
        return (ans+mod)%mod;
    }
};