2025-11-21：最大子数组 GCD 分数。用go语言，给出一个由正整数组成的 nums 和一个整数 k。你最多可以执行 k 次操作；每次操作选一个数组元素将其值乘以 2，且任意元素最多被翻倍一次（可以少于 k 次操作）。

在完成这些翻倍操作后，从数组中选取一个相邻的元素段（子数组）。该子数组的得分等于：子数组内所有数的最大公约数（GCD）与该子数组长度的乘积。请计算在不超过 k 次翻倍的前提下，能够获得的最大可能得分。

说明：

• “子数组”指数组中一段连续的元素。

• 数组的最大公约数指能整除该段所有元素的最大正整数。

1 <= n == nums.length <= 1500。

1 <= nums[i] <= 1000000000。

1 <= k <= n。

输入: nums = [5,5,5], k = 1。

输出: 15。

解释:

子数组 [5, 5, 5] 的 GCD 是 5，长度是 3。

因为翻倍任何元素都不能提高分数，所以最大分数是 3 × 5 = 15。

题目来自力扣3574。

🔍 算法步骤详解

1. 初始化阶段

• 计算最大位数 (mx)：首先确定数组中最大数值的二进制位数，用于后续lowbit（最低有效位）位置的记录。
• 创建lowbitPos数组：这是一个二维数组，用于记录每个lowbit（即数字二进制表示中最低位的1所在的位置，例如数字6的二进制是110，其lowbit是2）在数组中出现的位置索引。
• 初始化答案 (ans)：用于记录最终的最大得分，初始值为0。
• 初始化区间切片 (intervals)：用于维护以当前元素结尾的、具有相同GCD值的连续子数组区间信息。每个区间是一个结构体，包含三个字段：区间内所有元素的GCD值g，区间的左边界l（左开），以及右边界r（右闭），表示区间为(l, r]。

2. 遍历数组元素

算法从左到右依次处理数组nums中的每个元素x（索引为i），过程如下：

• A. 更新lowbitPos
  计算当前元素x的lowbit（即二进制末尾0的个数tz），并将当前索引i记录到lowbitPos[tz]对应的列表中。lowbit信息用于快速判断能否通过翻倍操作（乘以2等价于lowbit左移一位）来提升某个区间的GCD值。

• B. 更新区间GCD信息

  • 扩展现有区间：遍历intervals中所有已有的区间，将当前元素x与每个区间的GCD值p.g计算新的GCD，从而更新该区间的GCD值。这相当于将当前元素x纳入考虑，看看是否改变了以之前某个位置开始到当前i结束的子数组的GCD。
  • 添加新区间：将当前元素x自身作为一个新的区间（长度为1的子数组）添加到intervals中，其区间范围为(i-1, i]。

• C. 合并相同GCD的区间
  更新GCD后，相邻的区间可能拥有相同的GCD值。算法会合并这些连续的、GCD值相同的区间，只保留最后一个区间，并将其右边界扩展到被合并区间的右边界。这样做可以减少需要处理的区间数量，是优化效率的关键一步。

• D. 计算当前可能的最大得分
  经过合并后，intervals中的每个区间p代表了一系列以i结尾的子数组，这些子数组起始位置在(p.l, p.r]范围内，并且它们的GCD都是p.g。

  • 情况1：不进行翻倍操作
    对于区间p，最长的子数组是从p.l+1到i，长度为i - p.l。计算当前得分p.g * (i - p.l)，并尝试更新最大得分ans。
  • 情况2：考虑进行翻倍操作
    • 思路：翻倍一个元素（乘以2）可能提升整个子数组的GCD，特别是当这个元素的lowbit位置较低时（即二进制末尾0较少），翻倍后可能让整个子数组的GCD也翻倍（如果翻倍的元素是关键约束）。
    • 实现：对于区间p，其GCD值p.g的lowbit记为tz。我们从lowbitPos[tz]中查找在该区间(p.l, p.r]内，lowbit等于tz的元素位置。因为我们最多可以进行k次翻倍，理想情况下我们希望翻倍那些能使得区间GCD翻倍的元素。算法通过检查lowbitPos[tz]中倒数第k+1个元素的位置（如果存在的话）来确定一个左边界minL，使得在子数组(minL, i]内，我们至少有k个lowbit为tz的元素可以用于翻倍，从而可能将GCD提升至p.g * 2。
    • 计算得分：如果存在这样的minL（且minL < p.r，确保子数组长度大于0），则计算翻倍后的可能得分p.g * 2 * (i - minL)，并尝试更新ans。

3. 返回结果

遍历完整个数组后，变量ans中存储的就是在给定约束下（最多k次翻倍操作）能够获得的最大子数组GCD得分。

⏱ 复杂度分析

• 时间复杂度：O(n² log M)，其中n是数组nums的长度，M是数组中的最大值。

  • 主循环遍历n个元素。
  • 在每次循环中，需要更新intervals中所有区间的GCD。最坏情况下，intervals中可能包含O(i)个区间，但得益于GCD的单调性和合并操作，实际上区间数量会减少。GCD计算本身的时间复杂度为O(log M)。
  • 合并区间和计算得分的操作与区间数量线性相关。
  • 虽然存在嵌套循环，但由于区间合并优化，内层循环的整体负担在平均情况下会远低于O(n)。不过，在最坏情况下，每个元素都可能产生一个新的GCD阶梯，导致区间数量较多，因此保守估计为O(n² log M)。

• 额外空间复杂度：O(n log M)。

  • intervals切片：最坏情况下需要O(n)空间。
  • lowbitPos数组：大小为mx（约log M），每个列表最多存储O(n)个索引，总空间为O(n log M)。

这个算法通过动态维护GCD区间和巧妙利用lowbit信息，有效地探索了在有限翻倍操作下最大化得分的可能性。

Go完整代码如下：

package main

import (
	"fmt"
	"math/bits"
	"slices"
)

func maxGCDScore(nums []int, k int) int64 {
	mx := bits.Len(uint(slices.Max(nums)))
	lowbitPos := make([][]int, mx)

	ans := 0
	type interval struct{ g, l, r int } // 左开右闭 (l,r]
	intervals := []interval{}
	for i, x := range nums {
		tz := bits.TrailingZeros(uint(x))
		lowbitPos[tz] = append(lowbitPos[tz], i) // 用 tz 代替 x 的 lowbit

		for j, p := range intervals {
			intervals[j].g = gcd(p.g, x)
		}
		intervals = append(intervals, interval{x, i - 1, i})

		// 去重（合并 g 相同的区间）
		idx := 1
		for j := 1; j < len(intervals); j++ {
			if intervals[j].g != intervals[j-1].g {
				intervals[idx] = intervals[j]
				idx++
			} else {
				intervals[idx-1].r = intervals[j].r
			}
		}
		intervals = intervals[:idx]

		// 此时我们将区间 [0,i] 划分成了 len(intervals) 个左闭右开区间
		// 对于任意 p∈intervals，任意 j∈(p.l,p.r]，gcd(区间[j,i]) 的计算结果均为 p.g
		for _, p := range intervals {
			// 不做任何操作
			ans = max(ans, p.g*(i-p.l))
			// 看看能否乘 2
			tz := bits.TrailingZeros(uint(p.g))
			pos := lowbitPos[tz]
			minL := p.l
			if len(pos) > k {
				minL = max(minL, pos[len(pos)-k-1])
			}
			if minL < p.r { // 可以乘 2
				ans = max(ans, p.g*2*(i-minL))
			}
		}
	}
	return int64(ans)
}

func gcd(a, b int) int {
	for a != 0 {
		a, b = b%a, a
	}
	return b
}

func main() {
	nums := []int{5, 5, 5}
	k := 1
	result := maxGCDScore(nums, k)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

import math
from typing import List

def maxGCDScore(nums: List[int], k: int) -> int:
    if not nums:
        return 0
    
    mx = max(nums).bit_length()
    lowbit_pos = [[] for _ in range(mx)]
    
    ans = 0
    # 使用列表存储区间，每个元素是(g, l, r)
    intervals = []
    
    for i, x in enumerate(nums):
        # 计算x的trailing zeros（二进制末尾0的个数）
        if x == 0:
            tz = 0
        else:
            # x & -x 得到最低位的1，然后计算位数
            lowbit = x & -x
            tz = lowbit.bit_length() - 1
        
        if tz < mx:  # 确保不越界
            lowbit_pos[tz].append(i)
        
        # 更新已有区间的gcd
        for j in range(len(intervals)):
            g, l, r = intervals[j]
            intervals[j] = (math.gcd(g, x), l, r)
        
        # 添加新区间
        intervals.append((x, i - 1, i))
        
        # 合并gcd相同的相邻区间
        idx = 1
        for j in range(1, len(intervals)):
            if intervals[j][0] != intervals[j-1][0]:
                intervals[idx] = intervals[j]
                idx += 1
            else:
                # 合并区间，更新右边界
                g, l, _ = intervals[idx-1]
                intervals[idx-1] = (g, l, intervals[j][2])
        
        intervals = intervals[:idx]
        
        # 处理每个区间
        for p in intervals:
            g, l, r = p
            # 不乘2的情况
            ans = max(ans, g * (i - l))
            
            # 计算g的trailing zeros
            if g == 0:
                tz_g = 0
            else:
                lowbit_g = g & -g
                tz_g = lowbit_g.bit_length() - 1
            
            if tz_g >= mx:  # 超出范围，跳过
                continue
                
            pos = lowbit_pos[tz_g]
            min_l = l
            
            # 如果存在至少k+1个位置，取倒数第k+1个
            if len(pos) > k:
                min_l = max(min_l, pos[len(pos) - k - 1])
            
            if min_l < r:  # 可以乘2
                ans = max(ans, g * 2 * (i - min_l))
    
    return ans

# 测试代码
if __name__ == "__main__":
    nums = [5, 5, 5]
    k = 1
    result = maxGCDScore(nums, k)
    print(result)  # 输出结果

C++完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <bitset>
#include <cmath>

using namespace std;

int gcd(int a, int b) {
    while (a != 0) {
        int temp = a;
        a = b % a;
        b = temp;
    }
    return b;
}

long long maxGCDScore(vector<int>& nums, int k) {
    if (nums.empty()) return 0;

    int max_val = *max_element(nums.begin(), nums.end());
    int mx = max_val == 0 ? 1 : (int)log2(max_val) + 2;

    vector<vector<int>> lowbitPos(mx);

    int ans = 0;

    struct Interval {
        int g, l, r;
    };
    vector<Interval> intervals;

    for (int i = 0; i < nums.size(); i++) {
        int x = nums[i];

        // 计算尾随零的数量
        int tz = 0;
        if (x != 0) {
            while ((x & (1 << tz)) == 0) {
                tz++;
            }
        }
        if (tz < mx) {
            lowbitPos[tz].push_back(i);
        }

        // 更新所有区间的GCD
        for (auto& p : intervals) {
            p.g = gcd(p.g, x);
        }

        // 添加新区间
        intervals.push_back({x, i - 1, i});

        // 去重（合并GCD相同的区间）
        int idx = 1;
        for (int j = 1; j < intervals.size(); j++) {
            if (intervals[j].g != intervals[j-1].g) {
                intervals[idx] = intervals[j];
                idx++;
            } else {
                intervals[idx-1].r = intervals[j].r;
            }
        }
        intervals.resize(idx);

        // 处理每个区间
        for (const auto& p : intervals) {
            // 基本分数
            ans = max(ans, p.g * (i - p.l));

            // 检查是否可以乘以2
            int g_val = p.g;
            int tz_g = 0;
            if (g_val != 0) {
                while ((g_val & (1 << tz_g)) == 0) {
                    tz_g++;
                }
            }

            if (tz_g < mx) {
                const auto& pos = lowbitPos[tz_g];
                int minL = p.l;

                if (pos.size() > k) {
                    minL = max(minL, pos[pos.size() - k - 1]);
                }

                if (minL < p.r) {
                    ans = max(ans, p.g * 2 * (i - minL));
                }
            }
        }
    }

    return ans;
}

int main() {
    vector<int> nums = {5, 5, 5};
    int k = 1;
    long long result = maxGCDScore(nums, k);
    cout << result << endl;

    return 0;
}