891. 子序列宽度之和

891. 子序列宽度之和

题解：

1. 对于每个数a而言，其对res的贡献在于 a * a作为最大值的次数 - a * a作为最小值的次数
2. 先将数组排序
3. a 作为最大值的次数： a的下标为i， 比a小的数有 0 ~ i-1 总共i个数，则 为 $$2^i$$ 个
4. a 作为最小值的次数： a的下标为i， 比a大的数有 i+1 ~ n-1 总共i个数，则 为2^ n-i-1 个
5. 可以先对2的次方作预处理

public int sumSubseqWidths(int[] nums) {
        int mod = (int) (1e9 + 7);
        int n = nums.length;
        // 预处理2的n次方
        int[] p = new int[n + 1];
        p[0] = 1;
        for (int i = 1; i <= n; i++) {
            p[i] = (p[i - 1] * 2) % mod;
        }
        int res = 0;
        Arrays.sort(nums);
        // 对于每个数a而言，其对res的贡献在于 a * a作为最大值的次数   - a * a作为最小值的次数 
        for (int i = 0; i < n; i++) {
            res = (int) ((res + ((long) nums[i] * p[i] - (long) nums[i] * p[n - i - 1]) % mod) % mod);
        }
        return res;
    }