这是 LeetCode 3509 最大化交错和为 K 的子序列乘积 的 Rust 实现。解题思路这道题的核心难点在于不能直接用常规 DP 保留每个状态的最优解因为子状态的最优乘积与当前元素相乘后可能超出 limit但子状态中一个非最优的较小乘积反而可能合法且更优。因此采用 状态压缩 集合枚举 的思路- 用两个 HashMapi32, HashSeti32 分别记录奇数长度和偶数长度的子序列状态- key 为交错和value 为该交错和对应的所有可能乘积集合- 遍历每个数字时考虑三种情况1. 单独成序列长度1奇数长度2. 追加到奇数长度序列后 → 变为偶数长度交错和 减去 当前数3. 追加到偶数长度序列后 → 变为奇数长度交错和 加上 当前数- 乘积超过 limit 的状态直接丢弃- 最后从所有交错和为 k 的状态中取最大乘积Rust 代码rustuse std::collections::HashMap;use std::collections::HashSet;impl Solution {pub fn max_product(nums: Veci32, k: i32, limit: i32) - i32 {let n nums.len() as i32;let abs_k k.abs();// 剪枝理论最大交错和为 ((n1)/2) * 12if abs_k ((n 1) 1) * 12 {return -1;}// odd_len: 长度为奇数的子序列; even_len: 长度为偶数的子序列// key: 交错和, value: 该交错和对应的所有可能乘积的集合let mut odd_len: HashMapi32, HashSeti32 HashMap::new();let mut even_len: HashMapi32, HashSeti32 HashMap::new();for num in nums {// 复制当前状态let mut next_odd odd_len.clone();let mut next_even even_len.clone();// 1. 当前数字单独作为子序列长度1奇数长度if num limit {next_odd.entry(num).or_insert_with(HashSet::new).insert(num);}// 2. 追加到奇数长度子序列后 - 变为偶数长度交错和减去numfor (sum, products) in odd_len {let new_sum sum - num;// 剪枝超出合理范围则跳过if new_sum -900 || new_sum 900 {continue;}let new_products next_even.entry(new_sum).or_insert_with(HashSet::new);for p in products {let prod (p as i64) * (num as i64);if prod limit as i64 {new_products.insert(prod as i32);}}// 特殊处理 num 0 的情况if num 0 {new_products.insert(0);}}// 3. 追加到偶数长度子序列后 - 变为奇数长度交错和加上numfor (sum, products) in even_len {let new_sum sum num;// 剪枝超出合理范围则跳过if new_sum -900 || new_sum 900 {continue;}let new_products next_odd.entry(new_sum).or_insert_with(HashSet::new);for p in products {let prod (p as i64) * (num as i64);if prod limit as i64 {new_products.insert(prod as i32);}}// 特殊处理 num 0 的情况if num 0 {new_products.insert(0);}}odd_len next_odd;even_len next_even;}// 从奇数长度和偶数长度的结果中找出交错和为k的最大乘积let mut ans -1;if let Some(products) odd_len.get(k) {for p in products {ans ans.max(p);}}if let Some(products) even_len.get(k) {for p in products {ans ans.max(p);}}ans}}复杂度分析- 时间复杂度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. 乘积溢出计算乘积时使用 i64 避免 i32 溢出。4. Rust 的 HashMap 深拷贝使用 .clone() 即可实现深拷贝因为 HashMap 和 HashSet 都实现了 Clone trait。