这是 LeetCode 3509 最大化交错和为 K 的子序列乘积 的 Java 实现。解题思路这道题的核心难点在于不能直接用常规 DP 保留每个状态的最优解因为子状态的最优乘积与当前元素相乘后可能超出 limit但子状态中一个非最优的较小乘积反而可能合法且更优。因此采用 状态压缩 集合枚举 的思路- 用两个 MapInteger, SetInteger 分别记录奇数长度和偶数长度的子序列状态- key 为交错和value 为该交错和对应的所有可能乘积集合- 遍历每个数字时考虑三种情况1. 单独成序列长度1奇数长度2. 追加到奇数长度序列后 → 变为偶数长度交错和 减去 当前数3. 追加到偶数长度序列后 → 变为奇数长度交错和 加上 当前数- 乘积超过 limit 的状态直接丢弃- 最后从所有交错和为 k 的状态中取最大乘积Java 代码javaimport java.util.*;class Solution {public int maxProduct(int[] nums, int k, int limit) {int n nums.length;int absK Math.abs(k);// 剪枝理论最大交错和为 ((n1)/2) * 12if (absK ((n 1) 1) * 12) return -1;// oddLen: 长度为奇数的子序列; evenLen: 长度为偶数的子序列MapInteger, SetInteger oddLen new HashMap();MapInteger, SetInteger evenLen new HashMap();for (int num : nums) {MapInteger, SetInteger nextOdd deepCopy(oddLen);MapInteger, SetInteger nextEven deepCopy(evenLen);// 1. 当前数字单独作为子序列长度1奇数长度if (num limit) {nextOdd.computeIfAbsent(num, x - new HashSet()).add(num);}// 2. 追加到奇数长度子序列后 - 变为偶数长度交错和减去numfor (Map.EntryInteger, SetInteger entry : oddLen.entrySet()) {int sum entry.getKey();int newSum sum - num;if (newSum -900 || newSum 900) continue;SetInteger newProducts nextEven.computeIfAbsent(newSum, x - new HashSet());for (int p : entry.getValue()) {long prod (long) p * num;if (prod limit) newProducts.add((int) prod);}if (num 0) newProducts.add(0); // 0的特殊处理}// 3. 追加到偶数长度子序列后 - 变为奇数长度交错和加上numfor (Map.EntryInteger, SetInteger entry : evenLen.entrySet()) {int sum entry.getKey();int newSum sum num;if (newSum -900 || newSum 900) continue;SetInteger newProducts nextOdd.computeIfAbsent(newSum, x - new HashSet());for (int p : entry.getValue()) {long prod (long) p * num;if (prod limit) newProducts.add((int) prod);}if (num 0) newProducts.add(0);}oddLen nextOdd;evenLen nextEven;}int ans -1;if (oddLen.containsKey(k)) {for (int p : oddLen.get(k)) ans Math.max(ans, p);}if (evenLen.containsKey(k)) {for (int p : evenLen.get(k)) ans Math.max(ans, p);}return ans;}private MapInteger, SetInteger deepCopy(MapInteger, SetInteger map) {MapInteger, SetInteger copy new HashMap();for (Map.EntryInteger, SetInteger entry : map.entrySet()) {copy.put(entry.getKey(), new HashSet(entry.getValue()));}return copy;}}复杂度分析- 时间复杂度O(n \cdot S \cdot P)其中 S 为交错和的状态数约 [-900, 900]P 为每个和对应的乘积集合大小。由于 limit 5000 且 nums[i] 12实际状态数可控。- 空间复杂度O(S \cdot P)用于存储所有合法状态。关键注意点1. 0 的特殊处理当 num 0 时即使之前没有合法乘积追加 0 后乘积仍为 0合法需要单独加入。2. 交错和范围剪枝由于 nums[i] 12 且 n 150交错和范围约为 [-900, 900]超出此范围可直接剪枝。3. 乘积溢出计算乘积时使用 long 避免 int 溢出。