2025-09-30：最大化交错和为 K 的子序列乘积。用go语言，给出一个整数数组 nums 和两个整数 k、limit，要求|key|limit|下标|乘积|序列|整数

2025-09-30：最大化交错和为 K 的子序列乘积。用go语言，给出一个整数数组 nums 和两个整数 k、limit，要求从 nums 中选出一个非空的子序列（从原数组中挑选若干元素且保留它们的相对顺序），满足以下两点：

• 把选出的子序列从 0 开始重新编号后，偶数下标位置的元素之和减去奇数下标位置的元素之和等于 k（即“交替求和”等于 k）。
• 该子序列所有元素的乘积不得超过 limit。

在所有满足上述条件的子序列中，选择乘积最大的那个，并返回其乘积值；如果不存在任何满足条件的子序列，则返回 -1。

1 <= nums.length <= 150。

0 <= nums[i] <= 12。

-100000 <= k <= 100000。

1 <= limit <= 5000。

输入： nums = [1,2,3], k = 2, limit = 10。

输出： 6。

解释：

交错和为 2 的子序列有：

[1, 2, 3]

交错和：1 - 2 + 3 = 2

乘积：1 * 2 * 3 = 6

交错和：2

乘积：2

在 limit 内的最大乘积是 6。

题目来自力扣3509。

1. 总体思路

这是一个动态规划思路，但状态设计比较特殊。

我们考虑逐步处理nums的每个元素，维护两个字典（哈希表）：

•oddS：键是交错和s，值是另一个集合，存储以奇数长度结尾的子序列的乘积值。
•evenS：键是交错和s，值是另一个集合，存储以偶数长度结尾的子序列的乘积值。

为什么分奇偶长度？
因为交错和的符号取决于该元素在子序列中的位置（偶数下标加，奇数下标减），而位置奇偶性由子序列长度决定：

• 如果当前子序列长度是奇数，最后一个元素的下标是偶数（0-based），所以它应该加到交错和。
• 如果当前子序列长度是偶数，最后一个元素的下标是奇数，所以它应该减。

2. 初始化

•oddS和evenS初始为空。
• 总元素和total先算出来，如果|k| > total，说明不可能有解，直接返回 -1（因为交错和最大绝对值就是总和）。

3. 逐个处理元素

对nums中每个元素x：

3.1 从oddS生成新的偶数长度子序列

当前oddS里的子序列长度是奇数，如果加入x，新子序列长度变为偶数，那么x在奇数下标，所以交错和变化是-x，乘积是原来的乘积乘以x（如果不超过limit）。

遍历oddS的每个(s, 乘积集合)：

• 新和 =s - x
• 新乘积 = 原乘积 *x（如果超过limit则忽略）
• 把这些(新和, 新乘积)暂存到newEvenS中（因为不能立即更新evenS，否则会重复计算）。

3.2 从evenS生成新的奇数长度子序列

当前evenS里的子序列长度是偶数，如果加入x，新子序列长度变为奇数，那么x在偶数下标，所以交错和变化是+x，乘积是原来的乘积乘以x（如果不超过limit）。

遍历evenS的每个(s, 乘积集合)：

• 新和 =s + x
• 新乘积 = 原乘积 *x（如果超过limit则忽略）
• 更新到oddS[新和]的乘积集合中。

3.3 处理单独作为一个子序列

长度为 1（奇数长度），交错和 =x，乘积 =x（如果x <= limit），加入oddS[x]。

3.4 处理x = 0的特殊情况

如果x = 0，乘积会变成 0（且不超过 limit），需要单独考虑：

• 从evenS到oddS时，即使乘积超过 limit，但 0 总是允许的，所以加一个乘积 0。
• 从oddS到evenS时同理。

3.5 合并newEvenSevenS

把之前暂存的newEvenS合并到evenS中。

3.6 提前终止检查

如果oddS[k]或evenS[k]的乘积集合中有limit，说明已经找到乘积等于 limit 的解，可以直接返回 limit（因为这是可能的最大值）。

4. 最终结果

处理完所有元素后：

• 检查oddS[k]中的最大乘积值。
• 检查evenS[k]中的最大乘积值。
• 取两者最大值返回，如果都不存在则返回 -1。

5. 复杂度分析时间复杂度

• 外层循环：n（数组长度）。
• 内层循环：状态数由可能的交错和与乘积组合决定。
- • 交错和的范围是[-total, total]，其中total <= n * max(nums[i]) = 150 * 12 = 1800，所以范围约 3601 个可能值。
- • 乘积值不超过limit = 5000，所以每个和的乘积集合最多约 5000 个不同值。
• 最坏情况下，每个和都可能有很多乘积，但实际不会全部同时存在，因为每次扩展只乘一个较小数（0~12），乘积种类有限。
• 粗略上界：O(n * (total * limit))太大，但实际剪枝（乘积超过 limit 就丢弃）会大幅减少状态。
• 实际运行中，状态数受乘积增长限制，但最坏仍可能较大，不过题目 n=150 且 nums[i] 很小，所以可行。

空间复杂度

• 两个字典oddS和evenS，键的数量最多约2 * total + 1，每个键对应的乘积集合大小最多limit。
• 所以空间复杂度O(total * limit)，即约1800 * 5000量级（900 万），但实际不会满，因为乘积不会同时取满所有值。

最终答案（题目给的例子）：

• 输入nums = [1,2,3], k=2, limit=10
• 找到子序列[1,2,3]交错和 = 1 - 2 + 3 = 2，乘积 = 6，满足条件且最大，所以输出 6。

Go完整代码如下：

package main import (     "fmt" ) func maxProduct(nums []int, k, limit int)int {     total := 0     for _, x := range nums {         total += x     }     if total < abs(k) { // |k| 太大         return-1     }     // s -> {m}     oddS := map[int]map[int]struct{}{}     evenS := map[int]map[int]struct{}{}     add := func(m map[int]map[int]struct{}, key, val int) {         if _, ok := m[key]; !ok {             m[key] = map[int]struct{}{}         }         m[key][val] = struct{}{}     }     for _, x := range nums {         // 长为偶数的子序列的计算结果 newEvenS         newEvenS := map[int]map[int]struct{}{}         for s, set := range oddS {             newEvenS[s-x] = map[int]struct{}{}             for m := range set {                 if m*x <= limit {                     newEvenS[s-x][m*x] = struct{}{}                 }             }         }         // 长为奇数的子序列的计算结果 oddS         for s, set := range evenS {             if _, ok := oddS[s+x]; !ok {                 oddS[s+x] = map[int]struct{}{}             }             for m := range set {                 if m*x <= limit {                     oddS[s+x][m*x] = struct{}{}                 }             }             if x == 0 {                 add(oddS, s, 0)             }         }         // 用 newEvenS 更新 evenS         for s, set := range newEvenS {             if eSet, ok := evenS[s]; ok {                 for m := range set {                     eSet[m] = struct{}{}                 }             } else {                 evenS[s] = set             }             if x == 0 {                 add(evenS, s, 0)             }         }         // 子序列只有一个数的情况         if x <= limit {             add(oddS, x, x)         }         if set, ok := oddS[k]; ok {             if _, ok := set[limit]; ok {                 return limit // 提前返回             }         }         if set, ok := evenS[k]; ok {             if _, ok := set[limit]; ok {                 return limit // 提前返回             }         }     }     calcMax := func(m map[int]struct{})int {         maxVal := -1         if m != nil {             for v := range m {                 maxVal = max(maxVal, v)             }         }         return maxVal     }     return max(calcMax(oddS[k]), calcMax(evenS[k])) } func abs(x int)int {     if x < 0 {         return -x     }     return x } func main() {     nums := []int{1, 2, 3}     k := 2     limit := 10     result := maxProduct(nums, k, limit)     fmt.Println(result) }

Python完整代码如下：

# -*-coding:utf-8-*- def max_product(nums, k, limit):     total = sum(nums)     if total < abs(k):  # |k| 太大         return-1     # s -> set(products)     oddS = {}   # 长为奇数的子序列：交替和 s -> {product}     evenS = {}  # 长为偶数的子序列：交替和 s -> {product}     def add(m, key, val):         if key not in m:             m[key] = set()         m[key].add(val)     for x in nums:         # 由 oddS 扩展得到的新 evenS         newEvenS = {}         for s, prod_set in list(oddS.items()):             ns = s - x             if ns not in newEvenS:                 newEvenS[ns] = set()             for m in prod_set:                 prod = m * x                 if prod <= limit:                     newEvenS[ns].add(prod)         # 由 evenS 扩展得到的 oddS 更新         for s, prod_set in list(evenS.items()):             ns = s + x             if ns not in oddS:                 oddS[ns] = set()             for m in prod_set:                 prod = m * x                 if prod <= limit:                     oddS[ns].add(prod)             if x == 0:                 # 当加入 0 时，产生乘积为 0 的情况                 add(oddS, s, 0)         # 用 newEvenS 更新 evenS         for s, prod_set in newEvenS.items():             if s in evenS:                 evenS[s].update(prod_set)             else:                 evenS[s] = set(prod_set)             if x == 0:                 add(evenS, s, 0)         # 只有一个数的子序列         if x <= limit:             add(oddS, x, x)         # 提前返回的判断（达到上界 limit）         if k in oddS and limit in oddS[k]:             return limit         if k in evenS and limit in evenS[k]:             return limit     def calc_max(sset):         if not sset:             return-1         return max(sset)     return max(calc_max(oddS.get(k)), calc_max(evenS.get(k))) if __name__ == "__main__":     nums = [1, 2, 3]     k = 2     limit = 10     print(max_product(nums, k, limit))