2026-10-31：数对的最大强度。用go语言，给定一个整数数组 nums。需要从数组中选出两个位置不同的元素，组成一个数对。该数对的强度等于

2026-10-31：数对的最大强度。用go语言，给定一个整数数组 nums。需要从数组中选出两个位置不同的元素，组成一个数对。该数对的强度等于：这两个元素的乘积，除以它们的最大公约数的平方。请计算并返回所有可能数对中能够得到的最大强度值。

2 <= nums.length <= 2000。

1 <= nums[i] <= 100000。

输入： nums = [2,3,5]。

输出： 15。

解释：

选择 i = 1 和 j = 2，得到强度：

(3 * 5) / gcd(3, 5)2 = 15 / 1 = 15，这是所有数对中的最大值。

题目来自力扣4010。

大体步骤如下： 一、先看清”强度”这个式子的数学本质

数对 (x, y) 的强度定义为：

设 ，那么可以写成 ，且 。代入后：

结论：强度 = 两个数各自”约掉公因子之后”的乘积。所以要让它大，需要两个条件同时满足：

1. 两个数本身尽量大（乘积的分子大）；

2. 它们的最大公约数尽量小（除以的 小）。

顺带一个副产品： 一定能被 整除，所以代码里做整数除法 不会有任何取整误差，结果是精确的。这一点后面判断剪枝安全性时会用到。

题目数据范围 ，两两数对一共约 对，所以”全部枚举”本身是可行的baseline；这份代码的价值在于用一个上界剪枝把绝大多数情况压到远低于这个数。

二、整体策略：排序 + 构造一个”只依赖乘积”的上界

暴力枚举的问题是每一对都要算一次 。代码的思路是：

能不能在不算 的前提下，先判断”这一对绝对不可能刷新最优解”？如果能，就直接跳过不做 。

要做到这件事，需要两样东西：

•一个便宜的上界：只靠 就能算出”这对的强度最多是多少”；

•一个单调的枚举顺序：保证一旦上界跌破当前最优，后面所有候选只会更差，可以直接break，而不是继续遍历。

排序负责第二件事，全局 负责第一件事。

三、步骤 1：降序排序（为单调性铺路）

代码用slices.SortFunc配合比较函数b - a，把nums排成从大到小。

排序不是为了”找最大的两个数”这么简单（最大的两个数不一定是最优解，例如[15, 10, 6]中15×10的强度只有 6，而10×6的强度是 15）。排序的真正目的是让后面双重循环的枚举顺序具备单调性：

• 外层i递增时， 的值递减；

• 内层遍历nums[:i]，即下标 ，因为数组已降序， 的值也是递减的，而且恒有 。

于是对固定的 ，内层循环中乘积 随着 从nums[0]走到nums[i-1]是严格单调不增的。这个性质是break能够成立的前提。

补充一句副作用：这是原地排序，会直接打乱调用方传入的 slice 顺序；如果调用方还依赖原顺序，需要先拷贝一份。

四、步骤 2：求”全局 gcd”，构造合法上界

代码接着从头到尾把所有元素卷进一个gcd，得到allGcd，即整个数组所有元素的公共最大公约数，再平方得到allGcd2。

初始值是 0，而 （gcd函数里a = 0时循环一次都不进，直接返回b），所以第一次滚动等价于”把allGcd初始化成第一个元素”，这是标准的写法。由于 满足交换律和结合律，遍历顺序不影响结果。

关键的不等式推导：

1.allGcd整除数组里的每一个元素，所以它也整除 ，也整除 ；

2. 既然allGcd同时整除 和 ，那它必然整除 ；

3. 因此 ，进而 ；

4. 分子相同、分母更大 商更小，于是：

右边就是那个”便宜的上界”——它完全不需要知道这一对具体的 ，只要一次乘法一次除法就能算出来。而且它是”任意数对通用的”，对数组里所有数对同时成立。

还有个细节值得一提： 未必能被 整除（因为allGcd只是 的下界，不一定等于 ），所以mul / allGcd2是向下取整的整数除法。向下取整只会让这个上界更小（更紧），而不会让它失效—— 真实强度 依然成立吗？这里要小心方向：真实强度 （实数除法），而真实强度是整数，所以真实强度 。是的，因为一个整数若不超过实数 ，那它也不超过 。所以取整后的上界依然是合法上界，剪枝安全。

五、步骤 3：双重循环 + 上界剪枝

外层枚举 （从 0 到 ）， ；内层枚举 ， 。这样每个无序数对恰好被访问一次，不重不漏。

内层每一步做三件事：

1. 先算mul = x * y（一次乘法，极便宜）；

2. 算上界mul / allGcd2，与当前最优ans比较：

• 如果上界 ≤ ans：说明这对的真实强度 上界 ans，绝对不可能刷新最优；而且因为 继续往下走时mul只会更小、上界只会更低，后面所有 也都不可能刷新最优—— 于是直接break，连 都不用算。

• 如果上界 > ans：说明这对”还有希望”，这时才付出代价真正去算 ，再用 更新ans。

3.ans初始为 0，而题目保证元素 ，所以第一对的上界一定 ，不会一开始就误剪。

这个break的正确性完全建立在第四节的继承和第三节的单调性之上，缺一不可：

• 没有单调的枚举顺序（比如乱序），即使某一对的上界不达标，也不能推断后面的对不达标，就只能continue而非break，剪枝收益大打折扣；

• 没有合法上界，break就可能把真正的答案剪掉。

六、用nums = [2, 3, 5]完整走一遍

1.降序排序→[5, 3, 2]。

2.求全局 gcd： ， ， ，所以allGcd = 1，allGcd2 = 1。上界退化成”就是乘积本身”。

3.外层 i = 0：nums[:0]为空，内层不执行。

4.外层 i = 1， ：

• 内层 ：mul = 15，上界ans = 0，有希望 → 算 → 强度 →ans = 15。

5.外层 i = 2， ：

• 内层第一个 ：mul = 10，上界ans = 15→ 立刻break，剩下的 直接跳过。

6. 返回 15。

验证一下被跳过的两对： 强度 10、 强度 6，确实都小于 15，剪枝没有剪错。

七、这个剪枝到底有多强？（以及什么时候会失效）

有意思的是，这个剪枝存在一个”两难”结构，让它在绝大多数输入下都异常高效：

• 如果数对的 普遍很小→ 强度值很大→ans迅速涨到一个很大的数 → 上界很容易就撞上ans→ 剪枝极早触发；

• 如果数对的 普遍很大→ 说明元素之间共享大量因子 → 全局allGcd也倾向于变大 → 上界 被压得很低 → 上界本身就不容易超过ans→ 剪枝同样很早触发。

两个极端都利于剪枝，所以实践中内层循环往往每个 只跑一两次就break。

但它并非没有最坏情况：漏洞在于”全局 gcd 小、局部两两 gcd 大”的输入。典型构造是取一批大质数 ，令数组元素是这些质数的两两乘积 。任意两个元素共享一个质因子（局部 gcd ≈ 300），但任意三个元素的公共 gcd = 1（全局allGcd = 1）。此时：

• 上界 ，非常松；

• 而真实强度只有约 ，ans很小；

• 于是上界几乎永远大于ans，剪枝几乎完全失效，内层会跑满，退化成 次完整枚举。

即便如此， 时也就约 次 ，完全在限制内，所以这个上界分析上是 、实践上远好于 ，属于”稳赚不赔”的优化。

八、复杂度分析

记 数组长度（ ）， （ ）。

时间复杂度

• 降序排序： （原地 pdqsort，比较函数 ）；

• 求全局 gcd： 次欧几里得，单次 ，合计 ；

• 双重循环：迭代次数上界。每次迭代是 的乘法+比较，只有未触发剪枝的那些迭代才额外付一次 的 。因此最坏 ，剪枝生效时显著低于此。

总时间复杂度： ，由双重循环主导，即 。

由于 ，欧几里得的迭代轮数最多十几轮且常数极小，工程上可以直接视作 ；代入 即约 次基本运算，毫秒级。

额外空间复杂度

• 排序是原地的，不分配新数组；nums[:i]只是复用的切片头（三个机器字），循环中不产生堆分配；

• 排序递归栈 ；

•ans、allGcd、mul等均为 的标量。

总额外空间复杂度： ，全来自排序的递归栈；忽略栈则可视为 。

九、两个实现层面的小提醒

1.整数宽度：mul = x * y最大可达 ，已超出 32 位int。在 64 位平台上 Go 的int是 64 位，没问题；若在 32 位平台编译则会溢出，稳妥做法是把中间变量换成int64（函数返回值已经是int64，说明作者也考虑到了量级）。

2.原地修改：如第三节所述，排序会打乱传入的 slice，这是函数的可观察副作用。

Go完整代码如下：

package main

 import (
    "fmt"
    "slices"
)

 func maxPairStrength(nums []int)int64 {
    slices.SortFunc(nums, func(a, b int)int { return b - a })

     allGcd := 0
    for _, x := range nums {
        allGcd = gcd(allGcd, x)
    }
    allGcd2 := allGcd * allGcd

     ans := 0
    for i, x := range nums {
        for _, y := range nums[:i] {
            mul := x * y
            if mul/allGcd2 <= ans {
                break
            }
            g := gcd(x, y)
            ans = max(ans, mul/(g*g))
        }
    }
    returnint64(ans)
}

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

 func main() {
    nums := []int{2, 3, 5}
    result := maxPairStrength(nums)
    fmt.Println(result)
}

Python完整代码如下：

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

 from math import gcd

 def max_pair_strength(nums):
    # 按从大到小排序
    nums.sort(reverse=True)

     # 计算所有元素的整体 gcd
    all_gcd = 0
    for x in nums:
        all_gcd = gcd(all_gcd, x)

     all_gcd2 = all_gcd * all_gcd

     ans = 0
    for i, x in enumerate(nums):
        for y in nums[:i]:
            mul = x * y

             if mul // all_gcd2 <= ans:
                break

             g = gcd(x, y)
            ans = max(ans, mul // (g * g))

     return ans

 def main():
    nums = [2, 3, 5]
    result = max_pair_strength(nums)
    print(result)

 if __name__ == "__main__":
    main()

C++完整代码如下：

  

using namespace std;

 int gcd_int(int a, int b) {
    while (a != 0) {
        int t = b % a;
        b = a;
        a = t;
    }
    return b;
}

 long long maxPairStrength(vector nums) {
    sort(nums.begin(), nums.end(), greater());

     int allGcd = 0;
    for (int x : nums) {
        allGcd = gcd_int(allGcd, x);
    }
    long long allGcd2 = 1LL * allGcd * allGcd;

     long long ans = 0;
    for (int i = 0; i < (int)nums.size(); ++i) {
        int x = nums[i];
        for (int j = 0; j < i; ++j) {
            int y = nums[j];
            long long mul = 1LL * x * y;

             if (mul / allGcd2 <= ans) {
                break;
            }

             int g = gcd_int(x, y);
            ans = max(ans, mul / (1LL * g * g));
        }
    }
    return ans;
}

 int main() {
    vector nums = {2, 3, 5};
    long long result = maxPairStrength(nums);
    cout << result << endl;
    return0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。