Hard
题目描述
给你一个正整数数组 nums 和一个整数 k。
你最多可以执行 k 次操作。在每次操作中，你可以选择数组中的一个元素并将其值翻倍。每个元素最多只能翻倍一次。
连续子数组的分数定义为其长度与该子数组中所有元素的最大公约数（GCD）的乘积。
你的任务是从修改后的数组中选择一个连续子数组，返回可以达到的最大分数。
注意：
- 数组的最大公约数（GCD）是能整除数组所有元素的最大整数。
示例 1：
输入：nums = [2,4], k = 1
输出：8
解释：
使用一次操作将 nums[0] 翻倍为 4。修改后的数组变为 [4, 4]。
子数组 [4, 4] 的 GCD 是 4，长度是 2。
因此，最大可能分数是 2 × 4 = 8。
示例 2：
输入：nums = [3,5,7], k = 2
输出：14
解释：
使用一次操作将 nums[2] 翻倍为 14。修改后的数组变为 [3, 5, 14]。
子数组 [14] 的 GCD 是 14，长度是 1。
因此，最大可能分数是 1 × 14 = 14。
示例 3：
输入：nums = [5,5,5], k = 1
输出：15
解释：
子数组 [5, 5, 5] 的 GCD 是 5，长度是 3。
由于翻倍任何元素都不会改善分数，所以最大分数是 3 × 5 = 15。
提示：
- 1 <= n == nums.length <= 1500
- 1 <= nums[i] <= 10^9
- 1 <= k <= n
解题思路
这道题需要我们找到最优的翻倍策略来最大化子数组的GCD分数。
核心思路：
枚举所有子数组：由于数组长度不超过1500，我们可以枚举所有可能的连续子数组。
处理2的因子：题目提示中建议单独处理元素中2的因子。这是因为翻倍操作实际上是给元素增加一个2的因子，而GCD的计算中2的因子起关键作用。
优化策略：
- 将每个数分解为
nums[i] = odd[i] × 2^pow2[i]的形式 - 对于每个子数组，我们可以通过翻倍操作增加某些元素的2的幂次
- 子数组的GCD等于所有奇数部分的GCD乘以最小的2的幂次
- 将每个数分解为
动态规划思想：
- 对于每个子数组，计算不进行任何翻倍操作时的GCD
- 然后考虑如何分配k次翻倍操作来最大化GCD
- 关键观察：要最大化GCD中2的幂次，应该优先给那些2的幂次较小的元素进行翻倍
算法流程：
- 预处理每个数的奇数部分和2的幂次
- 枚举所有子数组
- 对每个子数组，计算奇数部分的GCD和2的幂次分布
- 贪心地分配翻倍操作来最大化最终GCD
- 更新全局最大分数
时间复杂度主要来自子数组枚举和GCD计算，通过合理的优化可以在时限内通过。
代码实现
class Solution {
public:
long long maxGCDScore(vector<int>& nums, int k) {
int n = nums.size();
long long maxScore = 0;
// 预处理：分离奇数部分和2的幂次
vector<int> odds(n);
vector<int> pow2s(n);
for (int i = 0; i < n; i++) {
int val = nums[i];
int pow2 = 0;
while (val % 2 == 0) {
val /= 2;
pow2++;
}
odds[i] = val;
pow2s[i] = pow2;
}
// 枚举所有子数组
for (int i = 0; i < n; i++) {
int gcdOdd = odds[i];
vector<int> currentPow2s;
for (int j = i; j < n; j++) {
// 更新奇数部分的GCD
gcdOdd = __gcd(gcdOdd, odds[j]);
currentPow2s.push_back(pow2s[j]);
// 计算当前子数组的最优分数
vector<int> sortedPow2s = currentPow2s;
sort(sortedPow2s.begin(), sortedPow2s.end());
int operations = min(k, j - i + 1);
// 贪心地分配翻倍操作
for (int op = 0; op < operations; op++) {
sortedPow2s[op]++;
}
// 计算最小的2的幂次（这决定了GCD中2的幂次）
int minPow2 = sortedPow2s[0];
// 计算GCD和分数
long long gcd = (long long)gcdOdd * (1LL << minPow2);
long long score = gcd * (j - i + 1);
maxScore = max(maxScore, score);
}
}
return maxScore;
}
};
class Solution:
def maxGCDScore(self, nums: List[int], k: int) -> int:
import math
n = len(nums)
max_score = 0
# 预处理：分离奇数部分和2的幂次
odds = []
pow2s = []
for num in nums:
val = num
pow2 = 0
while val % 2 == 0:
val //= 2
pow2 += 1
odds.append(val)
pow2s.append(pow2)
# 枚举所有子数组
for i in range(n):
gcd_odd = odds[i]
current_pow2s = []
for j in range(i, n):
# 更新奇数部分的GCD
gcd_odd = math.gcd(gcd_odd, odds[j])
current_pow2s.append(pow2s[j])
# 计算当前子数组的最优分数
sorted_pow2s = sorted(current_pow2s)
operations = min(k, j - i + 1)
# 贪心地分配翻倍操作
for op in range(operations):
sorted_pow2s[op] += 1
# 计算最小的2的幂次
min_pow2 = sorted_pow2s[0]
# 计算GCD和分数
gcd = gcd_odd * (1 << min_pow2)
score = gcd * (j - i + 1)
max_score = max(max_score, score)
return max_score
public class Solution {
public long MaxGCDScore(int[] nums, int k) {
int n = nums.Length;
long maxScore = 0;
// 预处理：分离奇数部分和2的幂次
int[] odds = new int[n];
int[] pow2s = new int[n];
for (int i = 0; i < n; i++) {
int val = nums[i];
int pow2 = 0;
while (val % 2 == 0) {
val /= 2;
pow2++;
}
odds[i] = val;
pow2s[i] = pow2;
}
// 枚举所有子数组
for (int i = 0; i < n; i++) {
int gcdOdd = odds[i];
List<int> currentPow2s = new List<int>();
for (int j = i; j < n; j++) {
// 更新奇数部分的GCD
gcdOdd = GCD(gcdOdd, odds[j]);
currentPow2s.Add(pow2s[j]);
// 计算当前子数组的最优分数
List<int> sortedPow2s = new List<int>(currentPow2s);
sortedPow2s.Sort();
int operations = Math.Min(k, j - i + 1);
// 贪心地分配翻倍操作
for (int op = 0; op < operations; op++) {
sortedPow2s[op]++;
}
// 计算最小的2的幂次
int minPow2 = sortedPow2s[0];
// 计算GCD和分数
long gcd = (long)gcdOdd * (1L << minPow2);
long score = gcd * (j - i + 1);
maxScore = Math.Max(maxScore, score);
}
}
return maxScore;
}
private int GCD(int a, int b) {
return b == 0 ? a : GCD(b, a % b);
}
}
var maxGCDScore = function(nums, k) {
const n = nums.length;
let maxScore = 0;
function gcd(a, b) {
while (b !== 0) {
[a, b] = [b, a % b];
}
return a;
}
function gcdArray(arr) {
let result = arr[0];
for (let i = 1; i < arr.length; i++) {
result = gcd(result, arr[i]);
}
return result;
}
// Try all possible subarrays
for (let i = 0; i < n; i++) {
for (let j = i; j < n; j++) {
const subarray = nums.slice(i, j + 1);
const length = j - i + 1;
// Try all possible combinations of doubling elements
const indices = Array.from({length}, (_, idx) => idx);
function tryDoubling(pos, remaining, current) {
if (pos === length) {
const g = gcdArray(current);
maxScore = Math.max(maxScore, length * g);
return;
}
// Don't double current element
tryDoubling(pos + 1, remaining, current);
// Double current element if we have operations left
if (remaining > 0) {
const doubled = [...current];
doubled[pos] *= 2;
tryDoubling(pos + 1, remaining - 1, doubled);
}
}
tryDoubling(0, k, [...subarray]);
}
}
return maxScore;
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(n²log(max(nums))) |
| 空间复杂度 | O(n) |
说明：
- 时间复杂度：枚举所有子数组需要O(n²)，对于每个子数组需要计算GCD和排序操作，总体为O(n²log(max(nums)))
- 空间复杂度：需要额外数组存储预处理结果和临时排序数组，空间复杂度为O(n)