Kimi LeetCode 3574. 最大子数组 GCD 分数 Java实现

以下是 LeetCode 3574. Maximize Subarray GCD Score（最大子数组 GCD 分数）的 Java 实现，基于枚举 + 数学的解法。

核心思路

关键观察：翻倍一个元素相当于给它乘一个因子 2。对于任意子数组，其 GCD 中因子 2 的个数取决于子数组中所有元素因子 2 个数的最小值。如果翻倍那些因子 2 个数最少的元素，GCD 中的因子 2 就可以增加 1。

因此，对于每个子数组，我们需要：
1. 计算子数组的 GCD
2. 统计子数组中各元素因子 2 的个数，找出最小值 `mi` 及其出现次数 `t`
3. 如果 `t <= k`，说明我们可以用不超过 k 次操作翻倍所有具有最小因子 2 个数的元素，从而使 GCD 翻倍（×2）；否则 GCD 不变

由于 `n <= 1500`，枚举所有子数组的复杂度 `O(n² × log n)` 是可以接受的。

Java 代码

```java
class Solution {
public long maxGCDScore(int[] nums, int k) {
int n = nums.length;

// 预处理：统计每个数中因子2的个数
int[] cnt = new int[n];
for (int i = 0; i < n; ++i) {
for (int x = nums[i]; x % 2 == 0; x /= 2) {
++cnt[i];
}
}

long ans = 0;

// 枚举所有子数组 [l, r]
for (int l = 0; l < n; ++l) {
int g = 0; // 当前子数组的GCD
int mi = 1 << 30; // 当前子数组中最小因子2个数
int t = 0; // 具有最小因子2个数的元素个数

for (int r = l; r < n; ++r) {
// 更新GCD
g = gcd(g, nums[r]);

// 更新最小因子2个数及其出现次数
if (cnt[r] < mi) {
mi = cnt[r];
t = 1;
} else if (cnt[r] == mi) {
++t;
}

// 计算得分：如果具有最小因子2个数的元素个数 > k，则无法全部翻倍，GCD不变
// 否则可以翻倍，GCD乘以2
long score = (r - l + 1L) * (t > k ? g : g * 2);
ans = Math.max(ans, score);
}
}

return ans;
}

// 欧几里得算法求GCD
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}
```

复杂度分析

- 时间复杂度：`O(n² × log(max(nums)))`
- 枚举所有子数组 `O(n²)`
- 每次计算 GCD 需要 `O(log(max(nums)))`
- 预处理因子 2 个数 `O(n × log(max(nums)))`

- 空间复杂度：`O(n)`，用于存储 `cnt` 数组

示例验证

输入 输出 解释
`nums = [2,4], k = 1` `8` 翻倍 `nums[0]` → `[4,4]`，GCD=4，长度=2，得分=8
`nums = [3,5,7], k = 2` `14` 翻倍 `nums[2]` → `[3,5,14]`，子数组 `[14]` 得分=14
`nums = [5,5,5], k = 1` `15` 无需翻倍，整个数组 GCD=5，长度=3，得分=15

参考来源：