LCM이 C++의 제품과 동일한 최대 길이 하위 배열

배열 A가 있다고 가정합니다. LCM이 해당 하위 배열 요소의 곱과 동일한 하위 배열의 최대 길이를 찾아야 합니다. 그런 종류의 하위 배열을 찾을 수 없으면 -1을 반환합니다. 배열이 {6, 10, 21}이고 LCM이 210이고 곱도 210인 하위 배열 {10, 21}이 있으므로 길이가 2라고 가정합니다.

접근 방식은 간단합니다. 길이가 2보다 크거나 같은 가능한 모든 하위 배열을 확인해야 합니다. 하위 배열이 조건을 만족하면 응답의 최대값과 하위 배열의 길이로 응답을 업데이트합니다.

예시

#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);
}

출력

Maximum Length: 3