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

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)
}

# -*-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))