Kimi LeetCode 3351. 好子序列的元素之和 Python3实现

```python
class Solution:
def sumOfGoodSubsequences(self, nums: List[int]) -> int:
MOD = 10**9 + 7
mx = max(nums) if nums else 0

# f[i] = 以值 i 结尾的所有好子序列的元素和
f = [0] * (mx + 1)
# g[i] = 以值 i 结尾的所有好子序列的数量
g = [0] * (mx + 1)

for x in nums:
# 1. 单独作为一个子序列
f[x] = (f[x] + x) % MOD
g[x] = (g[x] + 1) % MOD

# 2. 接在以 x-1 结尾的好子序列后面
if x > 0:
f[x] = (f[x] + f[x - 1] + g[x - 1] * x) % MOD
g[x] = (g[x] + g[x - 1]) % MOD

# 3. 接在以 x+1 结尾的好子序列后面
if x + 1 <= mx:
f[x] = (f[x] + f[x + 1] + g[x + 1] * x) % MOD
g[x] = (g[x] + g[x + 1]) % MOD

return sum(f) % MOD
```

核心思路：

- 好子序列要求相邻元素差的绝对值恰好为 1。处理数字 x 时，它可以：
1. 单独作为一个好子序列。
2. 接在所有以 x-1 结尾的好子序列后面。
3. 接在所有以 x+1 结尾的好子序列后面。

- `f[x]` 记录以值 x 结尾的所有好子序列的元素和，`g[x]` 记录对应的数量。
- 从 x-1 转移时，新增贡献为 `f[x-1] + g[x-1] * x`（原有子序列和 + 每个子序列末尾新增 x）。
- 最终答案为 `sum(f) % MOD`。

复杂度：
- 时间 O(n + M)，M = \max(\text{nums})。
- 空间 O(M)。