题目描述

原题链接

思路分析

朴素思路（超时）

通过回溯找到所有可能性，然后求解
套用回溯模板求解
此题范围过大，肯定超时

const int MOD = 1e9 + 7;

class Solution {
private:
    vector<vector<int>> total;
    vector<int> path;

    void process(vector<int>& nums, int index) {
        if (index == nums.size()) return ;
        for (int i = index; i < nums.size(); i++) {
            path.push_back(nums[i]);
            total.push_back(path);
            process(nums, i + 1);
            path.pop_back();
        }
    }

public:
    int sumSubseqWidths(vector<int>& nums) {
        process(nums, 0);
        int res = 0;
        for (auto& path : total) {
            int mi = path[0], mx = path[0];
            for (auto& v : path) {
                mi = min(mi, v);
                mx = max(mx, v);
            }
            res += (mx - mi);
        }
        return res;
    }
};

数学

考虑到宽度的定义为序列中最大值和最小值的差值，因此可以考虑每个数字对于最终结果的贡献
- 当数字作为最大值时，为正向贡献
- 当数字作为最小值时，为负向贡献
- 只需要计算出有多少种可能性即可
既然只需要关心数组nums中数字的大小而不需要关心它所在的位置了，所以先排序，方便进行计算可能性
排序之后，我们随便找一个下标为i的元素，可以找到以下规律
- 作为最大值：因为除下标为$i$的元素必选外，其余元素共$i$个（0和1），每个位置有两种可能性（选或者不选），因此结果为$2^i$
- 作为最大值：因为除下标为$i$的元素必选外，其余元素$n - i - 1$（3,4,6,7），每个位置有两种可能性（选或者不选），因此结果为$2^{n - i - 1}$
- 以nums[i]和其左侧所有元素拼装组合成的子序列示例：
最终贡献即为两者之和
以上图片来自参考1

const int MOD = 1e9 + 7;

class Solution {
public:
    int sumSubseqWidths(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        // 预存2的幂次
        vector<int> pow2(n);
        pow2[0] = 1;
        for (int i = 1; i < n; i++) pow2[i] = pow2[i - 1] * 2 % MOD;
        // long防止溢出
        long res = 0;
        for (int i = 0; i < n; i++) {
            res += long (pow2[i] - pow2[n - 1 - i]) * nums[i];
        }

        // 减法，可能有负数，消除负数影响
        return (res % MOD + MOD) % MOD; 
    }
};