最长乘积等价子数组

给你一个由 正整数 组成的数组 nums。
如果一个数组 arr 满足 prod(arr) == lcm(arr) * gcd(arr)，则称其为 乘积等价数组 ，其中：
prod(arr) 表示 arr 中所有元素的乘积。
gcd(arr) 表示 arr 中所有元素的最大公因数 ( GCD )。
lcm(arr) 表示 arr 中所有元素的最小公倍数 ( LCM )。
返回数组 nums 的 最长 乘积等价子数组的长度。

  • 输入： 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]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
var maxLength = function (nums) {
  // 计算最大可能的lcm为所有数字的lcm
  const maxLcm = nums.reduce((a, b) => lcm(a, b), 1);
  // 计算最大可能的gcd为数组中最大的数字
  const maxGcd = Math.max(...nums);

  const n = nums.length;
  let ans = 1;

  for (let i = 0; i < n; i++) {
    let prod = 1;
    let g = nums[i]; // 子数组的最大公约数
    let l = nums[i]; // 子数组的最小公倍数

    for (let j = i; j < n; j++) {
      prod = prod * nums[j];
      g = gcd(g, nums[j]);
      l = lcm(l, nums[j]);

      // 如果乘积大于最大可能的乘积，则不再继续计算
      if (prod > maxLcm * maxGcd) break;

      // 检查是否满足乘积等价条件
      if (prod === l * g) {
        ans = Math.max(ans, j - i + 1);
      }
    }
  }

  return ans;
};