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。
我们需要高效地计算所有好子序列的元素之和。直接枚举所有可能的子序列并检查其是否为好子序列显然不可行,因为子序列的数量是指数级的。因此,我们需要一种动态规划的方法来高效地计算。
f
数组:大小为 max(nums) + 3
,初始为0。cnt
数组:大小为 max(nums) + 3
,初始为0。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
。f
的和,并对 mod
取模。n
是 nums
的长度,m
是 nums
中的最大值。我们需要遍历 nums
一次,并且每次更新操作是 O(1) 的。f
和 cnt
数组的大小与 nums
的最大值相关。在最坏情况下,m
可以是 100,000。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)
}
# -*-coding:utf-8-*-
from typing importList
defsumOfGoodSubsequences(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))