2025-06-04：好子序列的元素之和。用go语言，给定一个整数数组 nums，一个“好子序列”是指该子序列内任意相邻的两个元素之间的绝对差为1。

子序列是由原数组中删除若干元素（也可以不删除）后，保持元素相对顺序不变得到的新序列。

任务是计算 nums 中所有可能的好子序列的元素之和。由于结果可能很大，需要将最后结果对 1000000007 取模。

注：长度为1的子序列视为好子序列。

1 <= nums.length <= 100000。

0 <= nums[i] <= 100000。

输入：nums = [3,4,5]。

输出：40。

解释：

好子序列包括：[3], [4], [5], [3,4], [4,5], [3,4,5]。

这些子序列的元素之和为 40。

题目来自力扣3351。

问题描述

我们需要计算给定整数数组 nums 中所有“好子序列”的元素之和。好子序列的定义是子序列中任意相邻的两个元素的绝对差为1。子序列是通过删除原数组中的若干元素（可以不删除）而保持剩余元素的相对顺序得到的序列。长度为1的子序列也被视为好子序列。由于结果可能很大，需要对结果取模 1,000,000,007。

解题思路

我们需要高效地计算所有好子序列的元素之和。直接枚举所有可能的子序列并检查其是否为好子序列显然不可行，因为子序列的数量是指数级的。因此，我们需要一种动态规划的方法来高效地计算。

具体步骤

1. 初始化：
   • f 数组：大小为 max(nums) + 3，初始为0。
   • cnt 数组：大小为 max(nums) + 3，初始为0。
2. 遍历 nums 中的每个数字 x：
   • 计算新子序列的数量：c = cnt[x] + cnt[x+2] + 1。
   • 更新 f[x+1]：f[x+1] = (f[x] + f[x+1] + f[x+2] + x * c) % mod。
   • 更新 cnt[x+1]：cnt[x+1] = (cnt[x+1] + c) % mod。
3. 计算所有 f 的和，并对 mod 取模。

时间复杂度和空间复杂度

• 时间复杂度：O(n + m)，其中 n 是 nums 的长度，m 是 nums 中的最大值。我们需要遍历 nums 一次，并且每次更新操作是 O(1) 的。
• 空间复杂度：O(m)，因为 f 和 cnt 数组的大小与 nums 的最大值相关。在最坏情况下，m 可以是 100,000。

Go完整代码如下：

package main

import (
	"fmt"
	"slices"
)

func sumOfGoodSubsequences(nums []int) (ans int) {
	const mod = 1_000_000_007
	mx := slices.Max(nums)
	f := make([]int, mx+3)
	cnt := make([]int, mx+3)
	for _, x := range nums {
		// 为避免出现 -1，所有下标加一
		c := cnt[x] + cnt[x+2] + 1
		f[x+1] = (f[x] + f[x+1] + f[x+2] + x*c) % mod
		cnt[x+1] = (cnt[x+1] + c) % mod
	}

	for _, s := range f {
		ans += s
	}
	return ans % mod
}

func main() {
	nums := []int{3,4,5}
	result := sumOfGoodSubsequences(nums)
	fmt.Println(result)
}

Python完整代码如下：

.

# -*-coding:utf-8-*-

from typing import List

def sumOfGoodSubsequences(nums: List[int]) -> int:
    mod = 10**9 + 7
    mx = max(nums)
    f = [0] * (mx + 3)
    cnt = [0] * (mx + 3)
    for x in nums:
        c = (cnt[x] + cnt[x + 2] + 1) % mod  # 下标+1的等效处理
        f[x + 1] = (f[x] + f[x + 1] + f[x + 2] + x * c) % mod
        cnt[x + 1] = (cnt[x + 1] + c) % mod

    ans = sum(f) % mod
    return ans

if __name__ == "__main__":
    nums = [3, 4, 5]
    print(sumOfGoodSubsequences(nums))