原题链接:
https://leetcode.cn/problems/sum-of-subsequence-widths/

贡献值法

  1. 子序列为去掉某个数后的序列 即不要求连续
  2. 只关注最大最小值 则与序列顺序无关
    由 1 2 分析可得我们可以对子序列排序后进行求解
    以排序后结果为 1 2 3 4 5 6 的序列为例
    对于4来说
    1 - 4 构成的序列均可选4 作为最大值
    4 - 6 构成的序列均可选4 作为最小值
    宽度值的定义为 最大值 - 最小值
    因此4 对于宽度值的贡献为
    [1 - 4]所构成序列中的所有最大值 - [4 -6]所构成序列中所有最小值
    根据乘法原理其贡献值为: 2 ^ (4) - 2 ^ (6 - 4) = 8
    将其进行推广则对排序后每个数x的贡献值为:
    x * 2^(i) - 2^(n - 1 - i) (其中i为x在排序后序列中的位置 n序列总长)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
package main

import (
	"sort"
)

const MOD int = int(1e9) + 7

func abs(x int)int{
    if x < 0{
        return -x
    }
    return x
}

func sumSubseqWidths(nums []int) int {
	n := len(nums)
	sort.Slice(nums, func(i, j int) bool {
		return nums[i] < nums[j]
	})
	// 预处理2的平方
	pow := make([]int, n)
	pow[0] = 1
	for i := 1; i < n; i++ {
		pow[i] = pow[i-1] * 2 % MOD
	}

	ans := 0

	for i, x := range nums {
		ans += x * (pow[i] - pow[n-1-i]) 
	}

    // 最后这里由于可能最后算出来是一个负数 
    // 所以要负数取模
	return (ans % MOD + MOD) % MOD
}