LeetCode-891. Sum of Subsequence Widths

LeetCode-891. Sum of Subsequence Widths

Given an array of integers ​​A​​​, consider all non-empty subsequences of ​​A​​.

For any sequence S, let the width of S be the difference between the maximum and minimum element of S.

Return the sum of the widths of all subsequences of A.

As the answer may be very large, return the answer modulo 10^9 + 7.

Example 1:

Input: [2,1,3]Output: 6Explanation:Subsequences are [1], [2], [3], [2,1], [2,3], [1,3], [2,1,3].The corresponding widths are 0, 0, 0, 1, 1, 2, 2.The sum of these widths is 6.

Note:

​​1 <= A.length <= 20000​​​​1 <= A[i] <= 20000​​

​​题解：​​

​​先排序，排序后，每个数中以A[i]为最小值的子数组出现次数是2^(n - i - 1) - 1次，以A[i]为最大值的子数组出现次数为(2^i) - 1次，那么最大值次数减去最小值次数就等于2^i - 2^(n - i - 1)，即每个A[i]贡献在总和之间的次数，用一个数组保存每个2^i;​​

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。