0891._Sum_of_Subsequence_Widths.md

891. Sum of Subsequence Widths

难度: Hard

刷题内容

原题连接

• https://leetcode.com/problems/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: 6
Explanation:
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

解题方案

思路 1 - 时间复杂度: O(NlgN)- 空间复杂度: O(N)******

• 我们逆向思路解决这个问题。结果要求最大数减去最小数的差之和，我们可以认为是，把所有的子序列的最大值累加，减去所有的子序列的最小值的累加值
• 数组中最大数，在子数组中也是最大数的，有2^(n-1)个子数组，同理，第二大数，在子数组是最大数的，有2^(n-2)个子数组，以此类推
• 同理，最小数也是这样计算
• 复杂度是O(nlgn)

代码：

class Solution {
    private static int MOD = 1000000007;

    private static int[] pow2;

    private void init() {
        if (pow2 == null) {
            pow2 = new int[20000];
            pow2[0] = 1;
            for (int i = 1;i < pow2.length;i++) {
                pow2[i] = pow2[i - 1] * 2;
                if (pow2[i] >= MOD) {
                    pow2[i] -= MOD;
                }
            }
        }
    }

    public int sumSubseqWidths(int[] A) {
        init();
        Arrays.sort(A);
        int ret = 0;
        for (int i = 0;i < A.length;i++) {
            ret += (long)A[i] * pow2[i] % MOD;
            if (ret >= MOD) {
                ret -= MOD;
            }
            ret -= (long)A[i] * pow2[A.length - i - 1] % MOD;
            if (ret < 0) {
                ret += MOD;
            }
        }
        return ret;
    }
}