题目描述

给你一个由 正整数 组成的数组 nums。

如果一个数组 arr 满足 prod(arr) == lcm(arr) * gcd(arr)，则称其为 乘积等价数组，其中：

• prod(arr) 表示 arr 中所有元素的乘积。
• gcd(arr) 表示 arr 中所有元素的最大公因数 (GCD)。
• lcm(arr) 表示 arr 中所有元素的最小公倍数 (LCM)。

返回数组 nums 的 最长 乘积等价子数组 的长度。

子数组 是数组中连续的、非空的元素序列。

术语 gcd(a, b) 表示 a 和 b 的 最大公因数。

术语 lcm(a, b) 表示 a 和 b 的 最小公倍数。

样例

输入： nums = [1,2,1,2,1,1,1]

输出： 5

解释： 

最长的乘积等价子数组是 [1, 2, 1, 1, 1]，其中 
prod([1, 2, 1, 1, 1]) = 2，gcd([1, 2, 1, 1, 1]) = 1，以及 lcm([1, 2, 1, 1, 1]) = 2。

输入： nums = [2,3,4,5,6]

输出： 3

解释： 

最长的乘积等价子数组是 [3, 4, 5]。

输入： nums = [1,2,3,1,4,5,1]

输出： 5

限制

• 2 <= nums.length <= 100
• 1 <= nums[i] <= 10

算法

(暴力枚举) $O(n^2 \log U)$

1. 暴力枚举子数组，先枚举起点，然后不断更新终点。
2. 当子数组乘积大于 $2520 \times 10$ 时，可以不再继续枚举，因为最小公倍数最大为 $2520$。

时间复杂度

• 共 $O(n^2)$ 个子数组，更新最大公约数和最小公倍数的时间复杂度为 $O(\log U)$，故总时间复杂度为 $O(n^2 \log U)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

const int U = 25200;

class Solution {
public:
    int maxLength(vector<int>& nums) {
        const int n = nums.size();

        int ans = 1;
        for (int i = 0; i < n; i++) {
            int prod = nums[i], l = nums[i], g = nums[i];
            for (int j = i + 1; j < n; j++) {
                prod = prod * nums[j];
                if (prod > U)
                    break;

                l = l * nums[j] / gcd(l, nums[j]);
                g = gcd(g, nums[j]);

                if (prod == l * g)
                    ans = max(ans, j - i + 1);
            }
        }

        return ans;
    }
};