Skip to content

3411. Maximum Subarray With Equal Products

  • Time: $O(n^2)$
  • Space: $O(1)$
 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
class Solution {
 public:
  int maxLength(const vector<int>& nums) {
    constexpr int kMaxLcm = 36'288'000;  // 10! x 10
    const int n = nums.size();
    int ans = 0;

    for (int i = 0; i < n; ++i) {
      int prod = 1;
      int l = 1;
      int g = 0;
      for (int j = i; j < n; ++j) {
        prod *= nums[j];
        if (prod > kMaxLcm)
          break;
        l = lcm(l, nums[j]);
        g = gcd(g, nums[j]);
        if (prod == l * g)
          ans = max(ans, j - i + 1);
      }
    }

    return ans;
  }
};

 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
32
class Solution {
  public int maxLength(int[] nums) {
    final int MAX_LCM = 36_288_000; // 10! x 10
    final int n = nums.length;
    int ans = 0;

    for (int i = 0; i < n; ++i) {
      int prod = 1;
      int l = 1;
      int g = 0;
      for (int j = i; j < n; ++j) {
        prod *= nums[j];
        if (prod > MAX_LCM)
          break;
        l = lcm(l, nums[j]);
        g = gcd(g, nums[j]);
        if (prod == l * g)
          ans = Math.max(ans, j - i + 1);
      }
    }

    return ans;
  }

  private int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
  }

  private int lcm(int a, int b) {
    return a * (b / gcd(a, b));
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
  def maxLength(self, nums: list[int]) -> int:
    n = len(nums)
    ans = 0

    for i in range(n):
      prod = 1
      l = 1
      g = 0
      for j in range(i, n):
        prod *= nums[j]
        l = math.lcm(l, nums[j])
        g = math.gcd(g, nums[j])
        if prod == l * g:
          ans = max(ans, j - i + 1)

    return ans