以下是 LeetCode 3574. Maximize Subarray GCD Score最大子数组 GCD 分数的 Java 实现基于枚举 数学的解法。核心思路关键观察翻倍一个元素相当于给它乘一个因子 2。对于任意子数组其 GCD 中因子 2 的个数取决于子数组中所有元素因子 2 个数的最小值。如果翻倍那些因子 2 个数最少的元素GCD 中的因子 2 就可以增加 1。因此对于每个子数组我们需要1. 计算子数组的 GCD2. 统计子数组中各元素因子 2 的个数找出最小值 mi 及其出现次数 t3. 如果 t k说明我们可以用不超过 k 次操作翻倍所有具有最小因子 2 个数的元素从而使 GCD 翻倍×2否则 GCD 不变由于 n 1500枚举所有子数组的复杂度 O(n² × log n) 是可以接受的。Java 代码javaclass 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; // 当前子数组的GCDint mi 1 30; // 当前子数组中最小因子2个数int t 0; // 具有最小因子2个数的元素个数for (int r l; r n; r) {// 更新GCDg gcd(g, nums[r]);// 更新最小因子2个数及其出现次数if (cnt[r] mi) {mi cnt[r];t 1;} else if (cnt[r] mi) {t;}// 计算得分如果具有最小因子2个数的元素个数 k则无法全部翻倍GCD不变// 否则可以翻倍GCD乘以2long score (r - l 1L) * (t k ? g : g * 2);ans Math.max(ans, score);}}return ans;}// 欧几里得算法求GCDprivate 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]GCD4长度2得分8nums [3,5,7], k 2 14 翻倍 nums[2] → [3,5,14]子数组 [14] 得分14nums [5,5,5], k 1 15 无需翻倍整个数组 GCD5长度3得分15参考来源