pythonclass Solution:def sumOfGoodSubsequences(self, nums: List[int]) - int:MOD 10**9 7mx 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) % MODg[x] (g[x] 1) % MOD# 2. 接在以 x-1 结尾的好子序列后面if x 0:f[x] (f[x] f[x - 1] g[x - 1] * x) % MODg[x] (g[x] g[x - 1]) % MOD# 3. 接在以 x1 结尾的好子序列后面if x 1 mx:f[x] (f[x] f[x 1] g[x 1] * x) % MODg[x] (g[x] g[x 1]) % MODreturn sum(f) % MOD核心思路- 好子序列要求相邻元素差的绝对值恰好为 1。处理数字 x 时它可以1. 单独作为一个好子序列。2. 接在所有以 x-1 结尾的好子序列后面。3. 接在所有以 x1 结尾的好子序列后面。- 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)。