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

乘积：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 处理 x 单独作为一个子序列

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

3.4 处理 x = 0 的特殊情况

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

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

3.5 合并 newEvenS 到 evenS

把之前暂存的 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))