Mảng con có độ dài tối đa với LCM bằng tích trong C ++

Giả sử chúng ta có một mảng A. Chúng ta phải tìm độ dài lớn nhất của mảng con, mà LCM của nó giống như tích của các phần tử của mảng con đó. Nếu loại mảng con đó không được tìm thấy, thì trả về -1. Giả sử mảng là {6, 10, 21}, thì độ dài là 2, vì mảng con {10, 21} ở đó, có LCM là 210 và tích cũng là 210.

Cách tiếp cận là thẳng về phía trước. Chúng ta phải kiểm tra mọi mảng con có thể có độ dài lớn hơn hoặc bằng 2. Nếu mảng con thỏa mãn điều kiện, thì hãy cập nhật câu trả lời dưới dạng tối đa của câu trả lời và độ dài của mảng con.

Ví dụ

#include <iostream>
using namespace std;
int gcd(int a, int b) {
   if (b == 0)
      return a;
   return gcd(b, a % b);
}
int maxLengthLCMSubarray(int arr[], int n) {
   int len = -1;
   for (int i = 0; i < n - 1; i++) {
      for (int j = i + 1; j < n; j++) {
         long long lcm = 1LL * arr[i];
         long long product = 1LL * arr[i];
         for (int k = i + 1; k <= j; k++) {
            lcm = (((arr[k] * lcm)) / (gcd(arr[k], lcm)));
            product = product * arr[k];
         }
         if (lcm == product) {
            len = max(len, j - i + 1);
         }
      }
   }
   return len;
}
int main() {
   int arr[] = {8, 2, 6, 10, 13, 21, 7};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Maximum Length: " << maxLengthLCMSubarray(arr, n);
}

Đầu ra

Maximum Length: 3