分别计算各元素对答案的贡献的思想

摘要: 通过一个问题看分别计算各个元素对答案的贡献的思想

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

各位好。在很多问题中，我们要在一组元素上求解一个全局的指标，通过对具体问题的分析之后，我们发现这个指标可以在元素的维度上进行分解。分解之后，我们就可以先对每个元素求一遍它对最终指标的贡献，然后再个这些贡献汇总起来，形成最终的答案。

这可以算是一个算法思想而不是一类具体的算法，我们要用这个思想解决问题的时候，需要分析具体的问题，找到如何将全局的指标分解为各个元素对答案的贡献，以及如何高效计算每个元素具体的贡献。

我们解决过很多问题都不知不觉用了这个思想，这里我们把文章 力扣2104-子数组的范围和 解决的这个问题回顾一下。我们解决了这样一个问题：一组数据的极差是统计学中比较常见的指标，给定一个数组，我们想计算它的所有子数组的极差的和是多少。

比较通常的思路是枚举每个子数组，然后问这个子数组上的最大值、最小值是多少。按照【将全局的指标分解为各个元素对答案的贡献】的思路，我们可以这样想：如果枚举每一个点，然后问该点可以作为多少个子区间的最大值，可以做多少个子区间的最小值。

假设对于数据点 nums[i]，有 n1 个子区间以它为最大值，有 n2 个子区间以它为最小值，则该数据点对答案的贡献是 nums[i] * (n1 - n2)，枚举所有的 nums[i] 将这些贡献相加即可得到最终答案。

本文我们用这种【将全局的指标分解为各个元素对答案的贡献】的思想解决一个类似的问题，与前面我们回顾的问题非常类似，只是把子数组改为了子序列，这一改动影响的只是高效计算每个元素的贡献用的具体算法。

---

题目

891. 子序列宽度之和

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

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

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

提示：

1 <= nums.length <= 1e5
1 <= nums[i] <= 1e5

示例 1：
输入：nums = [2,1,3]
输出：6
解释：子序列为 [1], [2], [3], [2,1], [2,3], [1,3], [2,1,3] 。
相应的宽度是 0, 0, 0, 1, 1, 2, 2 。
宽度之和是 6 。

示例 2：
输入：nums = [2]
输出：0

题解

算法: 分别计算各元素对答案的贡献

对于每个元素，问：该元素可以作为多少个子序列的最大值，可以做多少个子序列的最小值。

假设对于元素 nums[i]，有 n1 个子序列以它为最大值，有 n2 个子序列以它为最小值，则该元素对答案的贡献是 nums[i] * (n1 - n2)。

由于我们考察的是子序列的最大值和最小值，因此元素顺序对答案没有影响。我们可以首先将数组排序。然后再枚举每个元素，如下图：

假设当前枚举到元素 nums[i]，以该元素为最大值的子序列是这样的：nums[i] 必选，其余元素只能从 nums[0..i-1] 中选，选择方法有 $2^{i}$ 种。

类似地，以 nums[i] 为最小值的子序列，nums[i] 必选，其余元素只能从 nums[i+1..n-1] 中选，选法又 $2^{n-1-i}$ 种。

于是 nums[i] 对答案的贡献为 $2^{i} - 2^{n-1-i}$。过程中我们需要用到模下快速幂算法求 $2^{i}$ 模 MOD 的结果，直接看代码即可。

代码 (C++)

const int MOD = 1e9 + 7;
using ll = long long;

int quickpower_mod(int a, int n, int mod)
{
    int ans = 1;
    while(n)
    {
        if(n & 1)
            ans = ((ll)ans * a) % mod;
        a = (ll)a * a % mod;
        n >>= 1;
    }
    return ans % mod;
}


class Solution {
public:
    int sumSubseqWidths(vector<int>& A) {
        sort(A.begin(), A.end());
        int n = A.size();
        int ans = 0;
        for(int i = 0; i < n; ++i)
        {
            ans = (ans + (ll)A[i] * quickpower_mod(2, i, MOD)) % MOD;
            ans = (ans - (ll)A[i] * quickpower_mod(2, n - 1 - i, MOD) + MOD) % MOD;
        }
        return ans;
    }
};

---