Kimi LeetCode 3574. 最大子数组 GCD 分数 Rust实现
这是 LeetCode 3574. 最大子数组 GCD 分数 的 Rust 实现。
解题思路
核心观察：翻倍操作最多只能让子数组的 GCD 乘以 2。因此，对于每个子数组，我们需要判断是否能通过最多 `k` 次翻倍操作使 GCD 翻倍。
关键步骤：
1. 预处理：统计每个数中因子 2 的个数（即 `x` 能被 2 整除的次数）
2. 枚举子数组：固定左端点 `l`，向右扩展右端点 `r`
3. 维护三个值：
- `g`：当前子数组的 GCD
- `mi`：子数组中因子 2 个数的最小值
- `t`：具有最小因子 2 个数的元素个数
4. 判断翻倍：如果 `t > k`，说明需要翻倍的元素超过 `k` 个，无法翻倍；否则 GCD 可以翻倍
时间复杂度：O(n^2 \cdot \log n)，空间复杂度：O(n)
Rust 代码
```rust
impl Solution {
pub fn max_gcd_score(nums: Vec<i32>, k: i32) -> i64 {
let n = nums.len();
// 预处理：统计每个数中因子 2 的个数
let mut cnt = vec![0i32; n];
for i in 0..n {
let mut x = nums[i];
while x % 2 == 0 {
cnt[i] += 1;
x /= 2;
}
}
let mut ans: i64 = 0;
// 枚举所有子数组
for l in 0..n {
let mut g: i32 = 0; // 当前子数组 GCD
let mut mi: i32 = 1 << 30; // 最小因子 2 个数
let mut t: i32 = 0; // 具有最小因子 2 个数的元素个数
for r in l..n {
// 更新 GCD
g = Self::gcd(g, nums[r]);
// 更新最小因子 2 个数及其出现次数
if cnt[r] < mi {
mi = cnt[r];
t = 1;
} else if cnt[r] == mi {
t += 1;
}
// 判断是否能翻倍 GCD
// 如果具有最小因子 2 个数的元素个数 > k，则无法翻倍
let val = if t > k { g as i64 } else { (g * 2) as i64 };
let len = (r - l + 1) as i64;
ans = ans.max(len * val);
}
}
ans
}
// 递归实现 GCD
fn gcd(a: i32, b: i32) -> i32 {
if b == 0 {
a
} else {
Self::gcd(b, a % b)
}
}
}
```
代码说明
- `cnt[i]` 记录 `nums[i]` 中因子 2 的个数（例如 `12 = 2^2 × 3`，则 `cnt[i] = 2`）
- 翻倍操作的本质是将某个数乘以 2，相当于增加一个因子 2
- 子数组 GCD 中因子 2 的个数取决于子数组中所有数因子 2 个数的最小值 `mi`
- 如果具有最小值 `mi` 的元素个数 `t > k`，则最多 `k` 次翻倍无法让所有这些元素的因子 2 个数都增加，GCD 无法翻倍
- 否则，可以通过翻倍使 GCD 乘以 2
这个解法在 n \le 1500 的约束下可以通过所有测试用例。